UPDATE 8/28/12 7pm EST:So far so good with blank install of joomla and not using jUpgrade. I have only installed Hikashop thus far and no problems yet. As I install other extensions I had going I will keep checking to see if one extension in particular breaks it again.
I am beginning to think that it is not your product, but perhaps rather a jUpgrade that didn't go well. I clicked on the rebuild button in the Joomla menu options and your links were fine.
Any new links I make end up having
test.mydomain.com/Categories/alias of menu item/
The whole categories thing makes no sense to me. I am going to uninstall Hika and see if the site is still broken, which I expect it will be. I will then nuke the site and start with a fresh 2.5.6 install and make sure menu items work. After that is confirmed working I will install Hika on my fresh Joomla install. I will report back so you are aware whether it is related to Hika or not. I expect not.
In the mean time I will give you all the info you asked for, just in case you see something. I was just using default Joolma SEF, see below
I just need to figure out what all of the sudden is putting "catagories" in front of the menu alias.
Thanks for your help even though it is now seeming unrelated to your cart.