+1  A: 

Usually collation problems will cause your queries to run exceedingly slow, so it's important that everything is setup properly.

You have a database connection collation, a database collation and a table collation. Be sure all three are setup to utf8. If the problem persists, check your phpmyadmin configuration file and see what collation defaults are showing up.

Dooltaz
Thnx for the tip. I updated my question.
GaVrA
If you look on the front page of phpMyAdmin, you'll notice that when you create a new database, it has a setting for "MySQL connection collation:". Be sure when you create a new database that both that and the database collation are set to utf8. It may be as simple as recreating a new database, copying your current one to the new one, then renaming it. (assuming your database is fairly small)
Dooltaz
Dooltaz i updated my question, both of those are set on utf8_general_ci.
GaVrA
A: 

goto phpMyAdmin's folder look for config.inc.php. Open it and search for 'collation', probably arnd line 370 - change it to -

$cfg['DefaultConnectionCollation'] = 'utf8_unicode_ci';
Arpit Tambi
Hmm config.inc.php only have 26 lines and not one "collation"... :(
GaVrA