Foi um problema no arquivo de configuração. Estamos criando scripts de chef para fazer deploys, e usamos o pacote mysql do OpCode, que fez algumas coisas muito estranhas que bagunçaram o Mysql na máquina que não tínhamos esperado, configurando alguns valores de configuração para coisas que simplesmente não funcionavam.
Se estiver usando o chef, aconselho usar o pacote disponível no apt-get
package "mysql-server" do
action :install
end
package "mysql-client" do
action :install
end
Em seguida, altere a senha pelo código fornecido pelo OpCode ou altere-a após a instalação do servidor.
Isso foi no Rackspace com o Ubuntu 12.04 Server.