Is the Steam client online? If so, could it be partially blocked by a firewall?
Are you starting the game through Steam? As long as the client is running, though, the game should connect to make Steamworks functions available, even if you start it directly from the executable.
Are you shutting down all non-essential programs (especially anti-virus) before starting the game? Try exiting out of your firewall, if using a third party program.
You should be able to see online lobbies even if you have your own online game visibility set to Offline, so the in-game settings don't matter for that.