I've had this problem in the past and I replaced /etc/init.d/php-cgi with one that enables FastCGI and that stopped the problems. I think it's Ubuntu specific because I cannot recreate the problem (on a virtual server) on Debian.