Это указывает на несовпадающий набор символов между вашей базой данных (соединение) и фактическими данными.
Скорее всего, вы используете ISO-8859-1 на своем сайте, но MySQL считает, что он должен получить UTF-8.
http://dev.mysql.com/doc/refman/5.0/en/charset-connection.html описывает, что нужно проверить и как его изменить. Возможно, самый простой способ - выполнить запрос «SET NAMES latin1» при подключении к базе данных (при условии, что это необходимый набор символов).
Будучи фанатом Unicode, я бы предложил полностью перейти на UTF-8, но я понимаю, что это не всегда выполнимый вариант.
Редактировать: @markokocic: Сортировка только определяет порядок сортировки. Хотя это, конечно, должно соответствовать вашему набору символов, оно не влияет на диапазон символов, которые можно сохранить в поле.