Acho que encontrei a resposta. Eu baixei o pacote "python" real do Pacotes do Ubuntu e o instalei:
cd /tmp
wget http://nl.archive.ubuntu.com/ubuntu/pool/main/p/python-defaults/python_2.7.5-5ubuntu3_amd64.deb
sudo dpkg -i python_2.7.5-5ubuntu3_amd64.deb
Para concluir todo o processo, acabei recriando meu arquivo .deb personalizado (com python3.3) com um novo nome não conflitante ("python-to-remove") e, em seguida, instalei e desinstalei:
sudo dpkg -i python-to-remove_3.3.5-1_amd64.deb
sudo dpkg -r python-to-remove
Isso removeu todos os arquivos deste pacote, enquanto os arquivos de outros pacotes parecem não ter sido afetados. Acabei apagando um monte de arquivos de documentação também, mas nunca os usei antes, então acho que estou bem com isso.