Gemte du php-filen uden BOM ? Hvis ikke, så prøv det. Potentielle problemer med UTF-8 BOM
Prøv yderligere med 'utf-8' med enkelte anførselstegn og uden SET CHARACTER_SET
mysql_query("SET NAMES 'utf8'");
og med tegnsæt utf-8 i html-dokumentets overskrift:
header("content-type: text/html; charset=utf-8");