Ой, батенька... ума не приложу.
Обычно в проблеме с кодировками виноваты именно куки.
Потом еще бывает гон с MySQL
Апач тоже иногда пошутить любит
Короче, давай по-русски рассказывай, как обгонял, как подрезал... будем разбираться.