Это значит, что вместо mysql_query('SET NAMES utf8');
можно попробовать mysql_query('SET NAMES windows1251');
А вообще кодировка windows1251 - зло (имхо)
Бред. Кодировка базы не имеет никакого отношения к кодировке, в которой ты собираешься работать с данными.
В чем может быть проблема?
Кодировка твоего обращения к базе не соответствует кодировке, в которой отдаются страницы.
Один из вариантов решения, как уже сказали, сделать после подключения SET NAMES кодировка
P.S.
cp1251 вообще-то. Даже если windows1251 сработает - это будет везением, не все сборки серверов поддерживают этот псевдоним.