Проблемы с кодировкой в поисковиках

[Rainbow goblin]

У меня странная проблема с кодировками (я думаю). В общем,так: у меня многие поисковики отказываются искать строку запроса, набитую по-русски. Например, Яндекс, google. Хотя с Рамблером проблем нет. Впрочем, на английском Яндекс меня тоже не всегда воспринимает. Это и через Konqueror и через Mozilla и через Эпифани. Виснет, а потом пишет, что время ожидания истекло. Только на Интернет Эксплорер нормально реагирует (через cxoffice ставил).
Я уже и кодировку по дефолту в ядре менял и на разных версиях ядер пробовал и локализацию выставил - проблема осталась.
Посоветуйте что-нибудь, народ?