Это ожидаемое поведение. Удаление файлов - это не то же самое, что удаление пакета или программы.
Вы удалили все связанные с python вещи из своей установки, но ваш менеджер пакетов этого не знает. Когда вы снова заходите на установку Python, apt ожидает, что все эти файлы все еще будут там и не будут пытаться перезагрузить их. Что касается apt, все python все еще установлены; Вы никогда не говорили об этом иначе.
Вы можете попробовать следующее, чтобы попытаться исправить это: sudo apt-get install --reinstall python
В будущем удалите пакеты с помощью apt-get remove или apt-get purge или графически из программного обеспечения Ubuntu Software Center.