That is strange i've not seen one do that really, just to be clear when creating the new game/application you are making two? One for UDP and one for TCP and not using a range?
Basically here is the drill. Create a new application with the name WinMX1 and 2 or what not, use two different ports and make the range that single port ie
59998 - 59998 UDP and another new one for say
59999 - 59999 TCP ? or someit. and leave all other fields blank (the ones mentioned above)
Once this is done go back to the Gaming and Applications main page and use the drop down boxes to choose both the rules names' you made and set them to your computer name.
If these are all set correctly already then let me know we'll begin to investigate other things that could be blocking it.