If you want to use WordPress’ built-in menu, you probably have to play around wp_get_nav_menu_items (introduced in WP 3.0) to add extra classes to menu items.
I remember using xml parsers and custom walkers for the very same purpose, things have got just a little bit easier since that time.
The same problem — YARPP shows pages as related to posts. There’s no way to add tags or categories to pages…
Here’s my solution for 3 level navigation, based on @elbradford method:
$menu_string = wp_nav_menu($menu_args);
$xml = new SimpleXMLElement($menu_string);
$i = 0;
foreach($xml->li as $li) {
$classes = array('current-page-ancestor','current-menu-item','current-menu-parent');
if(strstr($li['class'],'current-page-ancestor') || strstr($li['class'],'current-menu-item') || strstr($li['class'],'current-menu-parent')) {
$out= $i;
};
$i++;
}
if(!empty($out)) {echo '<ul>'. $xml->li[$out]->asXML() . '</ul>';}