Modifica la codifica del database/tabella/colonna mysql in UTF-8 (e imposta anche le regole di confronto su un valore compatibile).
ALTER TABLE mytable CONVERT TO CHARACTER SET utf8 COLLATE utf8_general_ci;
ALTER TABLE mytable
MODIFY country CHAR(50)
CHARACTER SET utf8 COLLATE utf8_general_ci;
Specificare anche il set di caratteri sul lato PHP durante la connessione.
mysql_set_charset('utf8',$conn);
Dai un'occhiata a questo articolo per ulteriori informazioni e uno script per modificare in batch ogni tabella/colonna in un database.