Não sei por que sudo apt-get clean
não foi encontrado para você, mas uma maneira de liberar espaço é executar sudo apt-get autoremove
, que pode remover pacotes que não são usados por nenhum outro pacote (como um pacote instalado com outro pacote como dependência, mas o pacote que dependia dele não está mais instalado, desculpe se isso não faz muito sentido).
Uma outra maneira de liberar espaço é apenas reiniciar o computador. Isso (se bem me lembro) limpará todo o diretório / tmp, que armazena arquivos temporários.
Se o programa que cospe o erro não encontrado for sudo e não apto, você terá um problema muito mais sério em suas mãos, e a única maneira que eu posso pensar em restaurar o Aptitude (mais comumente conhecido como apt ou apt-get) é reinstalar o Ubuntu.
Espero que isso ajude.