Regarding the SNES setup guide found here: http://www.nhl94online.com/html/snes-zbattle-howto.shtml I think it should be mentioned that if TCP is required to play, then the host MUST be the player without the unsolved NAT issue. if BOTH players have unsolved NAT issues, they will be unable to connect even using TCP.
Also, for those who have Cisco Private Internet eXchanges (aka PIX Firewalls), the following are the commands to port forward both TCP and UDP port 7845 (obviously replacing values as necessary) :
access-list zsnes permit udp any host <publicIP> eq 7845
access-list zsnes permit tcp any host <publicIP> eq 7845
access-group zsnes in interface outside
static (inside,outside) udp interface 7845 <privateIP> 7845 netmask 255.255.255.255 0 0
static (inside,outside) tcp interface 7845 <privateIP> 7845 netmask 255.255.255.255 0 0