Виждам, че сте опитали това, но синтаксисът, който използвам е:mysql_query("SET NAMES utf8"). Синтаксисът ви може да е правилен, просто никога преди не съм го виждал.
Пример:
// connect to database stuff
$Connection = mysql_connect($server, $username, $password)
or die ("Error connecting to server");
// connect to database stuff
$db = mysql_select_db($database, $Connection)
or die ("Error selecting database");
mysql_query("SET NAMES utf8");