[The_Hinge]

The problem appears to be the multilingual support in the MySQL 5.0.* setup.

If that feature isn't turned on during the configuration process the account authentication barfs (industry term) with the above error.