I believe I have a solution. I had what seems to be the same problem--on a fully updated clean installation of Ubuntu 12.04.2 64-bit with the AMD 13.1 driver, I installed Steam and rebooted, and the system did not load.
At the Steam Community website, I found this thread by JohnV:
"Package dependencies cannot be resolved" workaround
I was able to reproduce one of the "Package dependencies cannot be
resolved" issues today. It happens if you install the Ubuntu 12.04.2
x64 build and then search and install Steam from the Ubuntu Software
Center. We are looking into this now.
Sorry we did not catch this earlier, but I think the 12.04.2 just came
out yesterday so we did not test it.
d2kx posted an answer:
@Valve: If you simply update Ubuntu 12.04/12.04.1, there are no
chances and Steam will work fine. The new Ubuntu 12.04.2 includes a
backported graphics/kernel stack from Ubuntu 12.10 so it works on
newer hardware. It uses packages that end with -lts-quantal (e.g.
xserver-xorg-core-lts-quantal). You need to adapt the dependencies of
the Steam .deb to reflect those changes and push the new version on
the website and the Ubuntu Software Center.