WordPress database error MySQL server has gone away

I have been dealing with a strange issue for the past two days. I hope I can give enough explanation so you have an idea of what is going on. I would be so greatly indebted to you if you could help me!!

I am getting the above error when someone comments on my blog (WordPress database error MySQL server has gone away). It brings up a 404 error page and the address displayed in the address bar says wp-comments-post, which makes me guess that’s where the error lies. If I am logged in as the admin and post a comment, it brings up a 500 error, again with the wp-comments-post. It really seems like it’s a problem with the redirect, but I’ve downloaded the wp.zip file and taken a fresh file out of there and uploaded it. Nothing.

The comment IS posted to the database and if you click the back button, the new comment is now at the bottom of the page. If it is the first comment on the post, everything seems to work normally.

I hadn’t changed anything in the settings or files from the time it was working to when it stopped working. I did have a scheduled post that went up, but other than that and some comments, no change to the database either.

Fixes I’ve tried:
-updating to WP 2.5.1
-updating all plugins
-deactivating plugins one by one to see if they are causing the problem
-deleting and reuploading the .htaccess file
-rolling back the server to when before the problem occurred (VERY weird that this didn’t fix it!)
-replacing the wp-comments-post file
-Bluehost performed an SSH test to determine that the DB is functioning as it should
-updated permissions on wp-comments-post to 755

PLEASE if you have any ideas, let me know so I can try them!

My blog is CreativeCurio.com.