Esse problema às vezes acontece porque a instalação do novo pacote substitui uma versão antiga (ou de outra forma diferente) e a desinstalação do novo pacote deixa você sem nenhuma das duas opções.
Talvez uma versão anterior do compat-wireless
tenha sido instalada antes que você instalou com checkinstall
. Em caso afirmativo, você deve reinstalar isso. Você pode verificar se foi ou não esse o caso olhando /var/log/dpkg.log
.