Problem with Menu/404

Hi, I'm kinda stuck and am hoping you have a solution. I'm a fairly advanced Joomla user (just to clear that up). So what happened is I Installed everything went ok, then I went to the menu, click on any of the menu links (cart/product/etc) and it flashes then immediately 404 error. So every menu link 404's and I can't figure out for the life of me why this would do it. There is nothing in my htaccess. What would cause that? If you could point me in the right direction that would be awesome. I've been scanning the forums but not coming up with anything. I have no SEO software running, base joomla 2.5.4. Joomla SEF is on and URL rewrite is on (with just the base htaccess) and extensions (html) are off.

I just did a test, if I turn Joomla core SEF off it all works. So apparently there is an issue with SEF? Am I missing a plugin or something? Anybody have the solution?

Hi,
I think that the problem is probably coming from the "menu" option of your modules