Well let's start with the basics then. Does WinMX even connect at all? Or can you connect? Can you search for files but just not download? Does it give any errors or just plain doesn't work?
What firewall do you use? Are you sure there isn't any others? Like software firewall along Windows firewall or hardware firewall/router? Try just turning OFF any and all firewalls. It's a quick way to tell, if it doesn't work, turn them back on.
Have you reached any sort of "in program" limits? Such as to many being shared? Or to many in your downloaded folder? Or to many trying to download?
Are people uploading FROM you? Are you sharing files?
Does the program require you to share files in order to download? If so, whether uploading or downloading, have you reached any bandwidth limits? Of course that doesn't apply if it's not connected at all.
Does the program's settings say anything about connections or proxy?
Does the program have an error log of some sort? Check that.
If not, if the program errors in any way, it may be recorded in Windows own error log. Right click My Computer and choose Manage. Then click the plus next to Event Viewer. Check under Application and System and see if there is any info there about your program.
Sorry for all the questions. Maybe it will help lead you somewhere.
Honestly I still think it may be a firewall issue. Even with an exception, it could be blocking traffic of some sort. Norton is notorious for this.