Se ainda não estiver, tente alterar a referência do seu repositório de pacotes para 'Principal' ou os Estados Unidos . Isso corrigiu meu problema de dependências não-preenchidas do Python-dev (minha instalação do 12.04 era usando o repositório de pacotes do Reino Unido, anteriormente).
- No 'Ubuntu Software Center' (USC), vá para o menu / guia 'Editar = > Fontes de Software '.
- Altere o valor suspenso "Fazer o download de" para "Servidor principal" ou um servidor nos Estados Unidos.
- Saia do USC, abra o 'Update Manager' do menu do programa do Ubuntu e 'Check' para atualização do software (ou edite 'sudo apt-get update' em uma janela de terminal).
- Atualize seu software como faria normalmente, por exemplo via 'Update Manager' ou apt-get / aptitude em um terminal.
Isso consertou meu repositório e eu instalei tudo o que eu precisava depois, como de costume.
Antes de corrigir meu problema com as instruções acima, vários comandos do aptitude / apt-get sugeriram que eu removesse muitos, muitos pacotes, mas, como você pode apreciar, eu não quis perder meus 6 meses + de pacotes adicionados, e isso é mesmo que eu tire um instantâneo da lista de pacotes às vezes (veja meu gist para dicas)! Estou muito feliz por ter descoberto as instruções que estou deixando aqui.
Espero que isso ajude.