Might it be the case that the tar archive gets created with a marker for the file but it's not actually added to it?

If tar fails to extract the files in the archive, you should start by finding out why. Perhaps you can play around with deb2tar and see what kind of tar file you get. If it looks broken, check how you create your package.

What tools are you using? Have you tried building the package with dpkg-deb --build <name of staging directory> ?