Red Hat Enterprise Linux ES release 4 (Nahant Update 8)
PHP 4.3.9 (cgi) (built: Nov 13 2010 16:10:31)
mysql Ver 14.7 Distrib 4.1.22, for redhat-linux-gnu (i386) using readline 4.3
SET NAMES 'utf8' is not enough for utf tables.
I had to use:
mysql_query("SET CHARACTER SET 'latin1'");
so that libmysql from php uses latin1 for the transport and the server translates it back to utf8.