Ola Amigo,
Talvez seja um pouco tarde, mas de toda forma, fica documentado aqui que eu tambem passei por isso, no 11.04.
O problema aconteceu após a instalação do Virtual Box, e de um usermod -G vboxusers xxxx.
Voce deve ter percebido que o acesso via terminal continua normal. De um sudo su na linha de comando, entre com a senha que voce tem certeza que digitou.
Depois disso, de um sudo passwd xxxx ou sudo passwd root, e digite uma senha nova.
Acabou o problema.
Agora se não for isso, realmente ferrou... No meu caso resolveu.