I'm not sure if this is the cause of your particular issue, but I do know that the makefile is created differently depending on whether Perl thinks you're using nmake/MSVC instead of dmake/gcc.

Run C:\>perl -V:cc and check its output. If it returns the path to nmake, that is almost certainly wrong if you are wanting to use the MingW gcc tools.
To Fix, move nmake to somewhere that is not in your PATH environment variable, {update} and ensure that the MingW tools is in your PATH. {/update} then rerun  C:\>perl -V:cc and it should return the path to gcc.exe. (may need to run it a second or third time sometimes until it does...)

Once that is configured correctly, just follow the standard mantra :

c:\temp>perl makefile.pl
c:\temp>dmake
c:\temp>dmake test
c:\temp>dmake install
[download]

(Also, i'd recommend using the gcc tools provided in the kit: ppm install mingw rather than downloading the tools individually as less fiddling is needed... The only hitch you might run into is that C:\perl\site\bin may not be in your PATH, in which case, just add it via System Properties > Advanced tab > Environment variables)

Updated: clarified post, and added extra detail...