Altere sua codificação de banco de dados/tabela/coluna mysql para UTF-8 (e também defina o agrupamento para um valor compatível).
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;
Especifique também o conjunto de caracteres no lado do PHP ao conectar.
mysql_set_charset('utf8',$conn);
Dê uma olhada este artigo para mais informações e um script para alterar em lote cada tabela/coluna em um banco de dados.
