Did you build the mysql gem with the correct version of the mysql client library? try the -- --with-mysql-config=/path_to/mysql_config option and make sure it is the right version?
Thanks Mukund- but that didn't do the trick either. This is what I did: sudo gem install mysql -- --with-mysql-config=/usr/local/mysql-5.1.37-osx10.5-x86/bin/mysql-config
Even went back and tried: sudo gem install mysql -- --with-mysql-dir=/usr/local/mysql-5.1.37-osx10.5-x86
Unfortunately nothing. Any other suggestions would be appreciated. I've
been tackling this for few days now and can't seem to resolve it. 
Mosses,
Did you had any luck? I am having the same problem. It does not happen when I connect to localhost as root it only happend on a remote server though. I tried multiple versions of mysql, 5+ and multiple ways of installing mysql gem without any luck.