Nandor, I've got a website that has both english and spanish. In my english.php file, I have @setlocale(LC_TIME, 'en_US'); and in my spanish.php file I have @setlocale(LC_TIME, 'es_ES');

This site works with a utf8_general_ci collation in my database and each of my main language files has define('CHARSET', 'utf-8');

I believe that it's the CHARSET value more than the locale value that's messing you up; make sure that all 6 of your main language files have the utf-8 value. Those are the files in the directories /includes/languages/YOUR_TEMPLATE and /YOUR_ADMIN/includes/languages directories.