If anyone else has this issue on Arch Linux (x86_64)

Tried playing as soon as it finished downloading, didn't get any warning/error message. I clicked play and diddly happened.

Restarted steam from shell so I could get some output(c'mon No output means all okay, if something goes wrong we _need_ to know about it ....) and saw this:

Code:

/home/hal_j/.SteamApps/common/Planetary Annihilation/PA: /home/hal_j/.local/share/Steam/ubuntu12_32/steam-runtime/amd64/usr/lib/x86_64-linux-gnu/libstdc++.so.6: version `GLIBCXX_3.4.17' not found (required by /home/hal_j/.SteamApps/common/Planetary Annihilation/PA)

After a few tries I finally found a quick workaround, apparently it's going fro the wrong libstdc++.so.6.(Adjust for your setup if you moved .SteamApps):

Code:

% ln -s /usr/lib/libstdc++.so.6 ~/.SteamApps/common/Planetary\ Annihilation/PA/

Good Luck, and Happy Hunting.
EDIT: changed cp to ln -s as it's a better option.

It's reported on official bugtracker here: FS#2100. Please vote!

Done, and as I mentioned on the reply I just made, it's likely better to do a symlink than cp, but I'm kinda hopeful that this workaround won't be needed for long.