Acabei de ter este problema ao instalar o Chrome e consegui que funcionasse. Se bem me lembro, a fonte dos problemas era a falta de dependências.
O comando que eu executei era sudo apt-get install -f , eu acho.
Eu deparei com a solução ao instalar algo através da linha de comando - o Ubuntu me disse que dependências estavam faltando e me deu os comandos para consertá-lo. Espero que isso ajude, embora meu problema não seja exatamente seu.