Seu computador não pode removê-lo porque outro aplicativo está usando o apt .
Você pode detectar e matar o processo que está usando o apt (pode ser o centro de software ou outro terminal instalando algo com o dpkg etc.).
Mas se você quiser uma maneira fácil: reinicie o computador :
Aqui está o código para remover todas as coisas sobre o redshift:
sudo apt purge '*redshift*'