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.
Meanwhile, if you are experiencing this problem, try downloading the 32-bit package directly from http://media.steampowered.com/client/installer/steam.deb
It should open in Ubuntu Software Center and install fine.
Oddly, if you install the 12.04.1 x64 build, then update the system, you will end up with 12.04.2, but you won't have that problem.
Sorry we did not catch this earlier, but I think the 12.04.2 just came out yesterday so we did not test it.
Update: this should all be resolved with the latest packages propped this weekend.