It could be their side too, you need to make sure both firewalls have the same settings. The second most common thing (especially since you are most likely behind a firewall/home router) is the router is not forwarding the ports to the correct machine. Just having it open isn't enough. The router needs to know where to send the information once it hits the router. It might not even have anything to do with your home setup and it is being blocked at your ISP, and may require a call to their tech support to make sure you get raw internet or at least that 5900 open. It also gets a lot more complicated and time intesive if you want to control multiple computers behind a single router from a remote location. This is a common problem with VNC and any of it's variations. But for a free program, can't beat it!
You can also try going to
www.logmein.com and try their service for free. I have the subscription based one and it works great since I can also transfer files and other system maintenance. The free version allows for just remote control, which I think is what you really want. It passes over port 80 like internet traffic and while the service is running, it keeps a lifeline to logmein's servers that will direct traffic to where you are. It is a gaurantee to work, the only caveat is some people do not like the idea of a central server having access to computers. (if logmein were to ever get successfully hacked, then that hacker would have access to everyone's desktops) But if you are willing to trust just a password and no username to gain desktop access to your computer, I don't think you would care much about this slight risk.