Eu tenho lutado com isso por algumas horas também, mas a resposta de Spiros funcionou para mim - depois eu pude fazer o login usando
mysql -uroot -p [enter]
(o que significa que a senha está em branco - eu, então, redefino a senha de root executando
sudo dpkg-reconfigure mysql-server-5.1
que solicita a senha do root. Então eu poderia entrar como acima com o usuário root e senha. Muito estranho que tenha instalado sem usuário root ... (mas está funcionando agora, obrigado Spiros!)