Hi madmav,
Sam maybe a bit premature in asking you to get the Vista Patch. The problem your reporting at this time wont be fixed by that.
It sounds like you actualy have either some software firewall or the Windows Firewall blocking the connection. WinMX will report that if your ports are not set properly in the settings so check those as well.
To be honest Im not 100% sure where to locate the Vista Firewal, more then likely its in the Control Panel and you should see an icon. Make sure you have WinMX on the list of exceptions and the ports added that your WinMX is using. TCP 6699 and UDP 6257 are defaults. Or disable this firewall if you usually have another one in use.
Then go to WinMX settings > Incoming TCP and make sure this is set to 6699 and then In/Out UDP and set that to 6257.
Then let us know how your doing.