I upgraded from 14.04 LTS to 16.04 LTS and also wasn't able to start Steam. It started (I mean, 'steam' continued to be running), but nothing happened after a few seconds.
For me, the workaround I finally found was to run Steam from commandline with:
Non-essential information below.
Steam provides essentially a "mini distribution" with it, called Steam Runtime, but it isn't currently doing a complete job so it somehow clashes with system C++ standard library and/or other libraries. During my experiments I had also a complaint of system libreadline6 <-> Steam runtime libtinfo5. After I manually unpacked the steam runtime tarball package under the Steam directory to overwrite what I previously had there, it changed to be as described in this problem (pcre_jit_stack_alloc).
An interesting tidbit is that before I found the solution above, I was able to start Steam so it downloaded an upgrade for itself by disabling the Steam Runtime temporarily with export STEAM_RUNTIME=0. Steam itself wouldn't run but that was my first step forward. I tried installing system equivalents of the 32-bit libraries required, but didn't finish / get it working.