Аз съм в Ubuntu 15.04 и получих същата грешка, както е посочено по-горе.
Направих :
sudo apt-get install libmysqlclient-dev
След това направих:
gem install mysql2
И сега мога успешно да направя
rails new <app_name> -d mysql
без никакви грешки.