Eu tive o mesmo problema ao usar pacotes recém-compilados em um servidor antigo (hardy) que não consegui atualizar. O dpkg-source não é responsável por criar um pacote .deb. Só é usado para criar o pacote fonte.
Na verdade, dpkg-deb cria os pacotes que normalmente são chamados por dh_builddeb in debian/rules . Você pode adicionar alterar este comando para dh_builddeb -- -Zgzip ou chamar dpkg-deb -Zgzip diretamente.
Se o comando dh_builddeb não estiver listado explicitamente no arquivo debian/rules
você pode adicionar as seguintes linhas para que funcione:
override_dh_builddeb:
dh_builddeb -- -Zgzip
Observe que antes da opção dh_builddeb há apenas uma guia, não vários espaços, pois isso é um Makefile .