Prueba a usar Synaptic en vez de Gdebi. En vez de bajarte los paquetes, deja que Synaptic los busque por ti en los repositorios. Deberás tener activado el repositorio
non-free. Si no sabes qué es un repositorio, es porque no has hecho caso a Ociomax, que te ha dado un enlace IMPORTANTÍSIMO. Léelo tres veces antes de continuar.