@Thaddeus it was over the Internet, we were in the same state just 500 miles apart so I don't think the region thing shouldn't be an issue (Washington state). Could be something with our firewalls but not too sure on how to check if that's the culprit? I can test more when I get home from work tonight. I'm also using the test appid for this.
It's likely a firewall issue if nobody is reporting problems with Steam's test appid. I've heard a lot of problems with in in China, but not here.
It is possible that maybe there's too many people using the test appid at the same time when you tested it. I can't remember off my head, but OnlineSessionPlugin only fetches so many sessions by default. The way the server browser works is by filtering out all non-matching sessions. That could be the issue. Or a firewall issue.
If you find out that it's a firewall thing and you plan on releasing a big commercial game, I think UWorks does NAT punchthrough. (To bypass firewalls without configuration) I haven't tried it since it's $109 on the marketplace, but I hear it's pretty good.