Rebuscando sobre este tema... Y ya para terminar de rizar el rizo, parece que el problema esta con las versiones superiores a la 3 de PhpMyAdmin.
He encontrado esta solución:
Cita: @mysql_query("SET NAMES 'utf8'");
A colocar justo después de la conexión con la bbdd. Y funciona :s
Saludos ;)