How to dynamically change the title of a menu item
Views doesn't implement hook_menu() to add it's items, it uses the menu link API directly to add links. This makes it a bit trickier to do what you want as hook_menu_link_alter() isn't necessarily called when the caches are flushed, but only when the link is edited via the admin UI.

The links in menus don't even necessarily go through theme_menu_link() so you can't override the title at the theme level with that hook. Instead the only way I could find to do it was to implement hook_preprocess_link(), check the path, and change the title.

It's not a very pleasing solution, as theme_link() seems far too generic a place to be hooking into to change just one link title, but it might do the trick:

function MYMODULE_preprocess_link(&amp;$vars) {
  if ($vars['path'] == 'newcomments') {
    $num_comments = MYMODULE_num_comments();
    $vars['text'] = format_plural($num_comments, '1 New Comment', '@count New Comments');
  } 
}


The only problem is that if there are other links on the page that point to the same URL their title will also be changed. Hopefully this can be a 'feature' rather than a 'bug' ;)