Acredito que sua instalação do MySQL seja de 64 bits (como o Windows), correto?

Ruby é de 32 bits, então você não pode vincular 32 bits a 64 bits .

Eu postei um artigo cobrindo as etapas de instalação no meu blog:

http://blog.mmediasys.com/2011/07/07/installing-mysql-on-windows-7-x64-and-using-ruby-with-it/

Essas etapas usam o MySQL Connector/C para solucionar os problemas de 32 bits versus 64 bits.

Ambos mysql ou mysql2 gem deve funcionar com isso.