O TrueCrypt não faz uma instalação muito complexa - nenhum banco de dados é modificado durante a instalação. O processo de instalação consiste em extrair vários arquivos e o processo de desinstalação consiste em excluir todos esses arquivos.
Se digitar sudo truecrypt-uninstall.sh
não corrigir, basta executar esta série de comandos:
sudo rm -f /usr/bin/truecrypt*
sudo rm -f /usr/share/applications/truecrypt*
sudo rm -f /usr/share/pixmaps/truecrypt*
sudo rm -rf /usr/share/truecrypt/
Depois disso, você pode querer reinicializar (embora possa não ser necessário) e continuar com a instalação como normal!