Like I said, I tried a bunch of different stuff before posting here... This is what it looks like without Cygwin in the path.

C:\Users\Name\Documents\Downloads\PLJava-0.04>perl makefile.pl
Set up gcc environment - 3.4.5 (mingw-vista special r3)
Writing Makefile for PLJava

C:\Users\Name\Documents\Downloads\PLJava-0.04>dmake
gcc -c -I"C:\PROGRA~1\Java\jdk1.5.0\include" -I"C:\PROGRA~1\Java\jdk1.
+5.0\includ
e/win32" -Wall -Wno-comments  -DNDEBUG -DWIN32 -D_CONSOLE -DNO_STRICT 
+-DHAVE_DES
_FCRYPT -DUSE_SITECUSTOMIZE -DPRIVLIB_LAST_IN_INC -DPERL_IMPLICIT_CONT
+EXT -DPERL
_IMPLICIT_SYS -DUSE_PERLIO -DPERL_MSVCRT_READFIX -DHASATTRIBUTE -fno-s
+trict-alia
sing -mms-bitfields  -I"C:\Perl\lib\CORE" PLJava.c
PLJava.c: In function `PLJava_eval':
PLJava.c:81: warning: unused variable `my_perl'
PLJava.c: In function `PLJava_eval_sv':
PLJava.c:95: warning: unused variable `my_perl'
PLJava.c: In function `PLJava_error':
PLJava.c:115: warning: unused variable `my_perl'
gcc -c -I"C:\PROGRA~1\Java\jdk1.5.0\include" -I"C:\PROGRA~1\Java\jdk1.
+5.0\includ
e/win32" -Wall -Wno-comments  -DNDEBUG -DWIN32 -D_CONSOLE -DNO_STRICT 
+-DHAVE_DES
_FCRYPT -DUSE_SITECUSTOMIZE -DPRIVLIB_LAST_IN_INC -DPERL_IMPLICIT_CONT
+EXT -DPERL
_IMPLICIT_SYS -DUSE_PERLIO -DPERL_MSVCRT_READFIX -DHASATTRIBUTE -fno-s
+trict-alia
sing -mms-bitfields  -I"C:\Perl\lib\CORE" PLJava_wrap.c
PLJava_wrap.c:39: warning: 'SWIG_JavaThrowException' defined but not u
+sed
C:\PROGRA~1\Java\jdk1.5.0\bin\javac -d ./  *.java
g++ PLJava.o PLJava_wrap.o -s   -L"C:\Perl\lib\CORE"  C:\Perl\lib\CORE
+\perl510.l
ib C:\MinGW\lib\libkernel32.a C:\MinGW\lib\libuser32.a C:\MinGW\lib\li
+bgdi32.a C
:\MinGW\lib\libwinspool.a C:\MinGW\lib\libcomdlg32.a C:\MinGW\lib\liba
+dvapi32.a
C:\MinGW\lib\libshell32.a C:\MinGW\lib\libole32.a C:\MinGW\lib\libolea
+ut32.a C:\
MinGW\lib\libnetapi32.a C:\MinGW\lib\libuuid.a C:\MinGW\lib\libws2_32.
+a C:\MinGW
\lib\libmpr.a C:\MinGW\lib\libwinmm.a C:\MinGW\lib\libversion.a C:\Min
+GW\lib\lib
odbc32.a C:\MinGW\lib\libodbccp32.a C:\MinGW\lib\libmsvcrt.a -shared -
+dll -o PLJ
ava.dll
'g++' is not recognized as an internal or external command,
operable program or batch file.
dmake:  Error code 129, while making 'PLJava.dll'

C:\Users\Name\Documents\Downloads\PLJava-0.04>
[download]

Update: Eugh, well, there's the problem, then. I updated MinGW to include g++ and now I get what you had before where dmake runs with no errors but dmake test fails:

C:\Users\Name\Documents\Downloads\PLJava-0.04>dmake test
C:\PROGRA~1\Java\jdk1.5.0\bin\java test
PLJava - Native code library failed to load. See the chapter on Dynami
+c Linking
Problems in the SWIG Java documentation for help.
java.lang.UnsatisfiedLinkError: PLJava_start
dmake:  Error code 129, while making 'test'
[download]