Chances are high YOU are doing it wrong, and not the tools everyone uses.
Do not fiddle with the encoding setting via queries! Use mysql_set_charset().
You have to repair all entries in your database that got there via PHP.
Note that "SET CHARACTER SET" is wrong, although it sounds like the right thing. If you cannot use the above PHP function, all you should do is use "SET NAMES utf8" only!