Предположу что может у Вас нет этого:
mysql_query("SET NAMES cp1251", $db);
хотя... , а вы где запускаете, в локале(denwer), или на сервере(у хостера)?
Зачастую на хостинге стоит принудительно кодировка в которую перекодируются все запросы, попробуйте изменить её на cp1251.