If you can confirm this using TwentyTen and no plugins, it might be worth posting in Trac.
I can confirm that this is an issue and a disturbing one. It basically boils down to the slug. On menus you can’t specify a slug. If you happen to create a menu with the title that matches a slug it gets the same id in the database. Later if you change the tag or menu title they both change. This can cause problems if you are asking for a menu by name or have links to /tag/tag-name. I don’t believe naming your menus some unorthodox name should be a requirement. Categories can get in the mix as well if you name a menu the same as a category slug and then rename either. Seems the menu creation isn’t creating its own taxonomy record to set itself a part from existing tags or categories.
Submitted a ticket
http://core.trac.wordpress.org/ticket/16936
Not sure if this is expected behavior or not. I could see one use for it, when displaying a category/tag post list being able to easily grab a corresponding menu if one exists. However, that seems more handy than a common need.