Why haven't I seen the <menu> element before?
http://reference.sitepoint.com/html/menu

Why does everyone recommend people markup the menu's in <ul>'s if there's a <menu> tag for that?
Because it can't contain block level elements validly?