Acho que a resposta aqui é que os pacotes criados com o checkinstall são hacks e não se espera que se comportem da mesma maneira que os pacotes Debian apropriados. Quando fui embora e criei o pacote corretamente usando o debhelper, isso não era mais um problema.