Hello TheBlackHole,
Which application or plugin set that cookie? That is going to be the offender.
Are you running Google Analytics or Web Stat by chance? Is anything installed on your server that does tracking? It could be that one of those tracking services are leaving cookies that start with _# this seems to be the common denominator, cookies with _# prefix cause the error.
I wish I could be of more help, this is a tricky one, working with trial and error.
Let me know if you are using any kind of tracking application.
Regards,