Read a lot more about the different cvars, and realized sv_searchkey was fucking us. Apparently every client has to have an identical search key to connect.
The trick is for the lobby leader to issue the following into the console
ms_force_dedicated_server “68.232.166.80:27015″
or put that line in your autoexec.cfg – we tried putting it in the config.cfg but steam cloud kept clearing it out!
Big thanks to Krackin for helping my troubleshoot this.