Running 'dmake' should have worked for you - it does for me with Strawberry Perl and Win32::Clipboard-0.56. (Update: I'm also running Windows Vista.)
First thing to do is (as already suggested) check that gcc is locatable - by running, eg, gcc -v

Other than that, the only thing I notice is that the output you posted indcates that perl Makefile.PL (and perhaps dmake, too) had been run earlier in that directory. When trying a re-build of a module in the same source directory, start with dmake realclean before running perl Makefile.PL
However, I doubt that will make any difference in this case.

Cheers,
Rob