Having a hard time with Cryllic and MySQL

[JREAM]

** We Fixed It, Just Deleted Tables * Reinstalled and it worked **

Im not too sure how this is happening..

I have my HTML charset=utf-8
I have my MySQL at utf8-general-ci
My PHP files are set to UTF8 without BOM

PHP Ver: 5
MySQL Ver: 5, and 4.1

When I connect to the database I do this:
mysql_query("SET CHARACTER SET utf8");
mysql_query("SET NAMES utf8");

Here are some characters
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
абвгдеёжзийклмнопрстуфхцчшщъыьэюя

But they show up as ??????? in the database and in the page.
A few other encodings did: –ЗИЙКЛМÐ�ОПРСТУФХÐ

I cant seem to find the right one or right way to get this going.

[Aleksejs]

Hi!
Is Cyrillic in fashion today?
http://www.sitepoint.com/forums/showthread.php?t=627396
Have you made sure that you execute:
SET names 'utf8'
save data to db and when you retrieve data from db?

[JREAM]

Hey there, yeah Cryllic is the new trend haha. We got it working after removing the database and reinstalling it, it wasnt working when we tried just setting it to utf8