A solução para mim é estranha.
Primeiramente, limpei a lista de apt, para ter certeza.
Em seguida, começou a verificar se havia um programa bloqueando-o (mesmo que não houvesse nada na memória que sugira isso): lsof|grep dpkg/lock
Então, finalmente, verifiquei se havia o arquivo de bloqueio na lista do apt. Nada.
Eu lembrei ontem que nós mudamos o ISP (temos 2 conexões ISP). Então, só para "voltar ao amor das origens" e mudar o provedor de volta.
Tudo funciona como deveria. aptitude, gerenciador de atualização, synaptic, software center e apt-get. Mas, então, uma nova pergunta: por que a mudança do ISP criou esse problema?