Yeah, Linux definately makes a better server, especially for a multithreaded game like UT2k4. But unless you are going to be running a high-capacity game server or multiple games on the same system, I'm sure Windows will work fine. That being said, it seems most people seem to be running UT2k4 dedicated servers on Linux, so I'm having a hard time finding a Windows howto for you.

It sounds to me like your problem is firewalling. You will need to do a little port forwarding on your router and open the same port on your server's software firewall (if any).