What ports do I need open to host a game?

Solution 1:

Borderlands 2 uses steamworks, and according to Chrisf they don't use any other special ports, so the standard steam answers apply.

Source

Steam Client

UDP 27000 to 27015 inclusive (Game client traffic)
UDP 27015 to 27030 inclusive (Typically Matchmaking and HLTV)
UDP 4380

Dedicated or Listen Servers

TCP 27015 (SRCDS Rcon port)

Steamworks P2P Networking and Steam Voice Chat

UDP 3478 (Outbound)
UDP 4379 (Outbound)
UDP 4380 (Outbound)

Also, there are several ISPs which block ports required for the proper operation of Steam and Steam games:

012.net (Steam traffic blocked)
Bluewin (Firewall blocks Steam from provider side - must be disabled through provider's service portal)
Dutch Telecom (Steam traffic blocked)
ISPFree (Steam traffic blocked)
Micronet Broadband (Steam traffic blocked)
TalkTalk (bandwidth throttling reduces download speeds)

Furthermore, Steam has their own connectivity support doc with the basic check your firewall, av software, etc. that you could try here.

The only interesting thing I see on it is starting steam with -tcp to force it to use all TCP ports instead of UDP, if that's messing something up on your end.

Solution 2:

EDIT: I forgot that Borderlands 2 is integrated with Steam unlike the first Borderlands, so @Kexlox answer has the correct information for fixing your problem.

An alternative is for you and your friends to download a program that emulates LAN. There are many programs that do this, including GameRanger and Hamachi. I personally recommend Tunngle, as it is what me and my friends currently use and it has support for a large range of games. Not that it's the best - but Tunngle will for sure get you and your friends playing. Don't forget to change from 'Friends Only' to 'LAN' in Network Settings in-game once you have set one of these programs up!