Some usernamed don't work, some do

Running 4.7.4 on PHP 5.1.6, Apache2 on Mandriva.
This is an established site that has been running for a couple of years, and was upgraded to 4.7.4 a couple of months ago.
We recently moved the site from an FC4 server, and seem to be having database problems.
Using Konqueror on Mandriva and Safari on a Mac, some user accounts work and others say "Sorry. Unrecognized username or password.", even when the password has just been set from an administrative account, or the account has just been created.

I notice that for one of the sites, all of the varchar() columns have collation set, either to utf8_general_ci or to latin1_sweedish_ci. That site is not having problems. For the site that is having problems, the tables have collation set (as above, to either character set), but the individual columns do not. I don't quite understand what effect this would have, but setting collation on the username and email fields fixed some of the log-in problems we were having. Something appears to have removed that setting again, but some accounts still work.

(Is there any point in or any way to batch-update the collation settings to something intelligent for a US site?)