MySQL 3.x is known to have some problems upper- and lower-casing certain (non-ASCII) characters.
An example (faulty) output of the Encoding Test is shown below:
Screenshot: Encoding Test Output

Upgrade to a newer version of MySQL. (4.1 is confirmed to work.)