I am testing virtuemart v2.0.1n on joomla 2.5.1 and I have created all menu items available by virtuemart. I do get the message:
Info: Assign the component VirtueMart to a menu item
..that, when I am at a virtuemart page. If I am on Joomla's home, I get:
Info: COM_VIRTUEMART_ASSIGN_VM_TO_MENU
not so nice so far

hope this gets fixed soon.
cheers and congrats for the great work so far.
p.s: who had the idea to mark topic as solved I dunno..
Update: Ok I tried something different and worked. Once I had the site to multilanguage mode, I didn't have any virtuemart menu item set to "Language > All". All vm menu items where in a specific language.
The message went away when I created a menu item "VirtueMart >> Front page >> Language > All".
At least that's how it works so far. Of course that menu item can be hidden and not shown anywhere but needs to be published.