Updating the category is a good test, but it won’t catch every possible error, only syntax errors.
I assume you’ve tried switching to the twentyeleven theme AND deactivating all of your other plugins?
Have you changed the core WordPress files? If not you won’t lose any customization by reinstalling WordPress (i.e. by copying the files over your existing installation). I mention that because I’ve had several cases where people write about ajax errors, only to find they’d accidentally modified their core files.
If you like, send a login and I’ll try to troubleshoot it for you.