I want to let you all still having trouble in-on what fixed the problem for me...
My issue was after performing an upgrade patch to the latest version, somehow my SEF URLS with sh404sef got tangled up when proceeding with the checkout steps because a new URL was generated for the process after replacing the files... Therefore, the itemID that Joomla gives the default page (IE - Home Page) in the menu (usually your main menu) is 1. So that being said, having the default menu item and its ID as 1 doesn't seem to work if you're having your VM front shop page associated with that item...
So what did I do?
I simply created a new menu item (turned off sh404SEF first, also purged all SEF URLS, and cleared Joomla cache) called "Shop" which Joomla automatically assigned a different itemID (in this case was 10), assigned it to simply the store front of VM, un-published the default menu item "Home", than set the "Shop" menu item as the default. I then erased the old default "Home" item. JOILA, that did it for me. I then turned SEF URLS back on and they worked without a hitch.
Just make sure to follow the steps I mentioned accordingly and this should work for you too. It's in essence what the MOD above said to do, just in a different, more specific fashion. I would also say that if your other URLS aren't working and not just the Store Front URL, then do the same thing and see if it helps.