I am using the fruitshop template, beez5, but not sample data (sample data was never installed). There are no menus pre-installed and no other menus with the same name/alias. I only have three menu items, Home, Testimonials and Contact.
(url for site is www.paintingbygerald.com
In 1.5 if I create a new menu item it defaults to last place and takes a first level place on the menu tree.
It seems that the same happens in 1.6 - the new menu item is not a sub-menu of anything. It points to a url and has a seemingly unique alias. That said, it is "contact-us" as an alias which generates the error. We originally had "contact-me" and wanted to use "contact-us". "contact-me" worked, as does "contact".
It may make sense code-wise, but doesn't make any sense on the user end that a menu alias I've never used is a duplicate and can't be used. Also there are no trashed menu items, so nothing I can fix to make it work as far as I can tell.