Eu tive exatamente o mesmo problema. No meu caso, o erro foi causado por ter um repositório de pacotes incorreto especificado. Com a ajuda do gerenciador de pacotes Synaptic, você pode descobrir qual é o problema: pressione Recarregar no Synaptic e aguarde os avisos. Em seguida, vá para Configurações - Repositórios e desative o repositório problemático. Espero que isso ajude alguém