Hmm, do you have access to the server error logs? Would be nice to get the actual error it's logging when the 404 comes up.

Also, does the 404 come up when you're clicking on something specific, like a post or page, or can it happen anywhere?