I have used the netplay of ZSNES quite a lot and I think it's excellent. Here's how it works for us: one person goes to the NETPLAY menu and clicks INTERNET, then START AS SERVER. Use the default port and don't uncheck the UDP connection checkbox. Then the other player goes to NETPLAY -> INTERNET and enters the other player's IP address into the server field. Then just click CONNET TO SERVER and it should work.
You can also try unchecking the UDP connection checkbox, but be sure that both of you do it. Also you should make sure that you are using the same version of the emulator. If you have an internal and an external IP address, try both of them. For example, ZSNES shows me my internal IP in the NETPLAY window but it doesn't work for me, I have to use the external one. Also be sure to disable any firewalls for the default port which is 7845. This is everything I can think of right now.