Я много имел дело с кириллицей, и это действительно сложно. До сих пор в моем опыте я не использовал COLLATION_CONNECTION. Все, что я делаю, это помещаю, как и вы, все возможные файлы в utf8. Затем поля в БД я помещаю в "utf8_unicode_ci" и использую только параметры SET NAMES для установки кодировки соединения. Этого должно быть достаточно. Имейте в виду, что имена Set могут быть хитрыми, так как только один лишний пробел, и он не будет работать. Я использую:
define("DBENCODING", "utf8");
mysql_query("SET NAMES '".DBENCODING."'", $this->connection);
Надеюсь, мне удалось помочь.