Did my webhost screw up? MySQL Upgrade vs Charset problem - urgent!

[Pedro Gomes]

Hello everyone.
First time posting here, but not for the best of reasons I'm afraid.

I have a somewhat large forum (about 500.000 posts and 5.000 users) using php+mysql.
Last saturday, the company where the forum is hosted, upgraded cPanel which in turn also required an upgrade on MySQL, which is now 4.1.21.

I'm far from an expert on chartsets and collations - to be honest I never really payed much attention to it, as everything has been working correctly - until now.

I don't know what they did, but the database, all tables and all text/char/varchar/etc columns have the collation set to cp1251_general_ci - that I didn't even know before this.
My problem is that of the forum *all* special chars appear as ???.
In phpMyAdmin they show up like:

nнvel (should be "nível")
Atenзгo (should be "Atenção")

I've been searching google but what I tried so far didn't work.

I suppose the correct charset should be latin1 with latin1_swedish_ci collation.
Of course I already tried setting a few columns to that collation, and the chars show up as literal "?" on MySQL, so I'm assuming the conversion failed and I lost data.

Can I still recover this data (convert it to the correct charset) with some procedure, or was it already corrupted with the default collation (cp1251_general_ci) that MySQL assumed?
I really hope that's not the case...

I do have a backup from a week before that and a backup that I did just after I noticed the problem.

In a worst case scenario, I could of course recover the first backup and try to merge some of the most recent data...

I would really appreciate some help, I'm getting a bit desperate about this.
Thank you.