Ok, i have done this 100 times. I created a menu and added items to it the menu is technically hidden.
and the menu items are published. I get 404'S!!! WTFunk. Anyone?
Did you create the menu module? I think after you do that, you publish the menu module to an imaginary position. That's off of the top of my head, so I could be wrong on all of that, just trying to help. I've had this same problem before.