I’m having this issue as well, and have performed all of the above troubleshooting suggestions, without a resolution. I have also tried activating new themes. The really strange thing is that spammers are still injecting comment spam from time-to-time, but legit registered users get a 404 when posting a comment. I’m totally stumped.
I’ve also tried replacing my theme’s comments.php file and my root wp-comments-post.php file. I am running 2.8.5, but the problem began with 2.8.1.
Any further suggestions will be greatly appreciated.