If you encounter this error again after upgrading to 12.04 (or for people arriving here after googling the title of this page after upgrading to 12.04), the following worked for me:
gem uninstall mysql2
gem install mysql2
This will recompile the gem using libmysqlclient18, and worked for me.