Drupal trying to add sessions multiple times

The website was working not too long ago. Then it suddenly stopped loading, returning only a blank white page. I assumed that there was an error on the page, and PHP was surpressing it. So I decided to enable E_ALL error reporting. Then I get this:

Fatal error: Duplicate entry '82a8f091fb7e9b05da074b1705c61f57' for key 1 query: INSERT INTO sessions (sid, uid, hostname, timestamp) VALUES ('82a8f091fb7e9b05da074b1705c61f57', 0, '209.204.144.148', 1184179879) in //includes/database.mysql.inc on line 75

I thought this was pretty interesting. This suggests to me that drupal thinks my sessionid is new, when it is in fact already in the database. So I removed my session from the table, and my pages start loading (though no completely). The pages return a bunch of notice errors, and session errors about headers already being set. This is probably due to the E_ALL setting.

However, once I refresh the page... the "Duplicate entry" error returns.

It seems very odd that such a serious error would pop up randomly. The only reason I can come up with is my hostings recent upgrade to PHP 4.4.7, though I fail to see how any kind of change in PHP's session handling would cause an error of this magnitude.

Any help would be appreciated.

Versions:
Drupal 4.6.6
MySQL 4.1.16-standard
PHP 4.4.7