Hi Rob, I just enabled SEF on your site using the SA details & faced the same
404 problems..
I hope you are using
SiteMap & that is what needs to be
regenerated, which would make all the new SEF rich URLs to be displayed in the browsers..
Let us know if you want us to proceed further with that... Standing by to assist..
