Não tenho certeza, mas o Ubuntu 18.04 usa o dpkg 1.19.0, que usa por padrão a compactação uniforme. Talvez o Travis CI não suporte isso.
--[no-]uniform-compression
Specify that the same compression parameters should be used for all archive members (i.e. control.tar and data.tar; since dpkg 1.17.6). Otherwise only the data.tar member will use those parameters. The only supported compression types allowed to be uniformly used are none, gzip and xz. The --no-uniform-compression option disables uniform compression (since dpkg 1.19.0). Uniform compression is the default (since dpkg 1.19.0).