Pode ser que o repositório "Parceiros da Canonical" não esteja ativado.
Vá até o Gerenciador de Pacotes Synaptic (Sistema, Administração, Synaptic); clique em Configurações e depois em Repositórios; na aba "Outros Softwares" certifique-se de que está marcado "Parceiros da Canonical". Caso não esteja, marque. Depois disso, vá até o terminal e digite sudo apt-get update e tente novamente.