This was fun day of debugging. I created a tarball of a package using PackageManager.Client.Pack() and tried to upload them to Bintray using npm publish.
Bintray returned a very useless 405 error. After unpacking the tarball and repacking it with the tar command on Linux I was able to upload it.
I switched to using SharpZipLib to create the tarball and now it publishes fine.
It seems that the tarball generated by PackageManager.Client.Pack() is in an uncommon format or has some errors.