Correctness of this is unclear. As Domas pointed out, people might be using something other than utf8 or binary.
This work with latin1 & binary (actually tested with latin1), and I don't remember mediawiki offering any other options. I can't fix this if I don't know what is wrong.
Also, whatever solution we come up, it would be nice to have it in 1.16.
Setting to new.
UTF-8 and binary are the only options. We used to have a latin1 option, which involved storing UTF-8 text in a latin1 field, a feat which could only work on MySQL 4.1+ if you're using binary as the client character set. I removed that option from the installer a while ago, since it breaks backups and is generally useless.
MediaWiki has not supported character sets other than UTF-8 for storage or display since 1.5.