|Welcome to the Monastery|
I've installed a fair number of modules under Windows NT. The first thing you need to check is that perl is in your PATH environment variable. It's conceivable that although an association is set up for files ending .pl to find the perl binary, it's not in your path. If not, I would recommend modifying your user environment variables in Start|Control Panel|System|Environment, if you're under NT. If it's W98, I guess I'd put it in autoexec.bat, or somesuch.
Once you have the tools in place, installing Perl modules under Windows is little different than installing under *nix. I probably have about 25 "after-market" modules installed, that I've had no problems. I have had one or two that are poorly written that wouldn't install easily, but they're really the exception.
Windows FTP has to be one of the lamest FTP clients around. There are several good ones, such as WSFTP. You'll find that they work a lot better (and more importantly, support passive mode, if you're behind a firewall that doesn't permit non-passive FTPs). You can find these at www.tucows.com.
If you require a compiler to build a module (as opposed to a pure perl module), you'll definitely need a compiler. My understanding is that you'll need whatever release of compiler was used to build your Perl binary. I don't have any experience with any other than the MSVC C++, so I can't say with any authority if that's true or not.
The fact that the module doesn't work after hacking up the makefile is no big surprise. My experience says those are touchy things to go hacking in. I'm sure the Perl gurus can casually create a makefile for installing, but I have to h2xs or MakeMaker.
And as a final note, allow me to compliment on the information provided to help track down your problem. This is the kind of information that encourages people to spend the time helping. Kudos!