The cause of this issue is that dpkg expects tar archives to be the GNU format, and does not understand the PAX format. In Go1.8 (and in Go1.9), I disabled path prefix splitting because the behavior was entirely buggy. This prevented the tar package from being able to use the USTAR format (which dpkg still understands), but forced it to use PAX to represent the longer file names. The inability to have control over the output format is the root issue here since both GNU and PAX are popular variants of tar.

For this reason, I filed #18710. In Go1.10, you will be able to explicitly specify that the output format is GNU, which will make dpkg happy again.

Confirmed the tip works to translate from PAX -> GNU (at least for this use in the godeb tool). Thanks @dsnet

in := tar.NewReader(...)
out := tar.NewWriter(...)
defer out.Close()
for {
	h, err := in.Next()
	if err == io.EOF { break }
	h.Format = tar.FormatGNU
	h.PAXRecords = nil
	out.WriteHeader(h)
	if h.Typeflag == tar.TypeDir { continue }
	w, err := io.Copy(out, in)
}