Кодировка везде одинаковая:

MySql
Тип: MyISAM
Кодировка: utf8_general_ci

PHP файлы
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
mysql_query("set names 'utf8'", $dbd);
mysql_query("SET CHARACTER SET 'utf8'")

.htaccess
AddDefaultCharset utf-8

выведи текст запроса на экран. Обработанный

Kusss, еще раз спасибо за помощь.

Как оказалось, в подключении к базе нужно было указать следующие строчки

mysql_query('set character_set_client="utf8"');
mysql_query('set character_set_results="utf8"');
mysql_query('set collation_connection="utf8_general_ci"');

С ними все работает.

Kusss, еще не подскажите, 1)как сделать поиск по отдельным словам.
Я знаю, что нужно применять команды explode и implode, но как грамотно их встроить в код поиска, я не знаю.

    $clean_search = str_replace(',', ' ', $query);
    $search_words = explode(' ', $clean_search);
    $final_search_words = array();
    if (count($search_words) > 0) {
      foreach ($search_words as $word) {
        if (!empty($word)) {
          $final_search_words[] = $word;
        }
      }
    }
	
    $where_list = array();
    if (count($final_search_words) > 0) {
      foreach($final_search_words as $word) {
        $where_list[] = "title LIKE '%$word%'";
      }
    }
    $where_clause = implode(' OR ', $where_list);