Help, I've been getting this error after upgrading

I've been getting this error after upgrading to 1.5.6.4. I've searched this forum and google for possible solutions but none works.

PHP Warning: session_start(): The session id is too long or contains illegal characters, valid characters are a-z, A-Z, 0-9 and '-,' in /home/xxxxx/public_html/system/library/session.php on line 12

By the end of the day, my error log is filled with this error. I've contacted my host and they said that it's server related. I've spent several days on this and can't seem to find a solution.

Can you help me? Thank you.