I have a similar problem even though I installed through the software center.
I removed Steam from Ubuntu software center (by uninstalling it with the gui) and also ran sudo apt-get remove steam.
After that I installed steam by sudo apt-get install steam and it worked for me. Albeit the steam logo that gets installed is the old logo. One might also have to move or remove the .steam file but this is after the installation anyways.
Still doesn't work for me, using sudo apt install steam gives the same thing.
Recently installed kubuntu 16.04 64-bit from scratch and I am getting the same error. Any fix on this?
I have solved this issue by changing the repository server from another country to United States.
Confirmed, should report the bug to Ubuntu on lanuchpad then since it's from their local repositories.
Nothing extracted yet.
After trying the .deb file from the official website for Ubuntu, Steam fails to install because of some problems with dependences on Ubuntu 16.04 LTS - 64x Bit.
I hope there will be a fix for this.