Well, I've been having much better success connecting to my buddy in the Internet custom games.  Part of this came from the latest updates (it still takes a while to connect, but now it consistently does), but also from how my friend rearranged his firewall settings.

Before, he had all of his traffic from his LAN coming out on his default IP.  Since he had an extra unused static IP, he decided to port redirect it to his gaming workstation.  Voila!  Immediately after his did that his success rate for connections improved dramatically.  Before we connected perhaps one out of 5 attempts, and now he's connecting consistently (if slowly).  Note that he still used the same amount of bandwidth; he just made sure the Demigod activity was separated from the rest.

I realize that many people may not have "spare IP addresses" to use; however, it is a reminder to check what other traffic may be in use on that IP.  It's possible that cutting down on activities using that same external IP can help your connection.

Trivial perhaps, but hopefully it will help someone.