What is the file extension of your perl script? If it is .pl try changing it to .cgi - a different server may not recognise the .pl extension as an executable file.
good point katgirl. If you are working w/ more than one language, it might help to name them .pl.cgi so that you know the cgi script was written in perl. if windows will let you do that.