Thanks for reaching out to us, first can you test the things pointed out on our Testing for Conflicts page? Normally issues like yours tend to be theme or plugin conflicting of some sorts.
You can also refer to the Knowledge base article about 404 Errors which might solve your issue, if none of that works please don’t hesitate to reply to us here and I will try my best to solve your issue.
Aha – found out the client had just updated some plugins. De-activated WordPress SEO 1.7.1 and things are working again. Do you guys have known bugs with that plugin?
Not that I’m aware of, but I will test it, rest assured. I’m also glad that you resolved your issue, if in the future you have issues again don’t hesitate and come here to the forum.