It looks like the problem is solved. Django creates one (1) connection to database and reuses it to handle requests. Multithreaded FastCGI creates threads to handle requests. These threads make requests to MySQL, which gets confused and loses its coolHHonnection. This process is random and compounded with multiple web requests at the same time. For example, if Google Web Accelerator decided to prefetch some pages, your web site would be hosed.
Luckily, the only place, which needs fixing, is one small class: mysql.DatabaseWrapper.
I added a dictionary of connections so every thread will have it’s own connection. Apparently it solved the problem. Additionally I ping connection to make sure it is not timed-out, and do some simple clean up, when threads are finished.
PostgreSQL doesn’t have this problem. For those of you keeping score at home, MySQL loses a cookie point.