У меня была эта проблема, и после попытки всего, что я обнаружил, это происходит, если вы устанавливаете mysql после того, как вы установили rails.
Переустановка рельсов решила проблему для меня.
Конечно, этот совет актуален только в том случае, если ответ iain не решил вашу проблему; -)