Ok, i spent the whole day reading these forums and I am probably the only person on earth who's red just about everything. :)
I have a brand new WordPress 3.5 that works like a charm, besides that it refuses to display Greek characters, all I get is ????? in both front and back ends. It does display Cyrillic, though!
I also have its entire database set to utf8_general_ci, including: general settings(phpMyAdmin 1st screen->MySQL connection collation), database (phpMyAdmin/database1/operations->collation), and finally I manually set up all the tables in the database (phpMyAdmin/database1/table1/operations->collation).
*All the above were adjusted after "the famous 5min self-installation". :-)
wp-config.php says :
/** Database Charset to use in creating database tables. */
Themes tested: twenty-ten, twenty-eleven, twenty-twelve, and page lines.
And finally for those who would blame the hosting, I have another site under the same hosting account, set up with Joomla 2.5, totally Greek and have never had any problems whatsoever.