Did you install the 32bit version or the 64? On twinery.org, "Linux" links to the 64 bit version, with ( 32-bit) linking to the other. (The download button should also link to the 64 bit version, if your browser is identifying itself properly.) The main thing is to make sure you have the right one. That's assuming you're running 64 bit, of course. The archive should be:
twine-2.1.3_linux64.zip
Then unzip it somewhere and run the Twine binary in the new location.
If you run it from console, the output should be more informative on which libraries it is looking for.
I'm on ubutu 16.10 yakkety and had no problem running it, but I also have a lot of development headers and libraries installed.