You just need to open your 6112 Port, and then start the game up.
Enter BattleNet, it'll tell you that it doesn't work,
If you open the port correctly, you should not get this error at all.
But just hit ESC, pick Battle net again, and bam, now it works.
Hell, for all I know perhaps you don't even need to open that port, but you do need to do that forward-back-forward dance to get into BattleNet for some odd reason.
You are probably triggering a NAT hole punch, which will get you past the battle.net UDP diagnostic, but will not actually let you host games. Joining games will work fine. To host, you need to allow unsolicited inbound packets. If you were allowing them, you would not need to iterate the connection attempt.
Then, at least for me and my rl friend, there can be issues of trying to join game where it says that the latency is poor. But there's another baffling way to fix that, which involves you creating a game. your friend try to join it and fail, then friend create a game and you try to join that, and now it's likely that you'll be able to join it.
This is another manifestation of the NAT hole punch. The described workaround is time sensitive. You must complete the dance before the respective routers purge their list of expected responses.
obviously doesn't work fine if you have to do a bunch of hocus pocus.....
It works as documented. It may not be as convenient as modern games, but back then, that was how things worked and people got along fine.