Okay, so this isn't exactly a bug, but I couldn't find a mailing list for PerlBin, so I decided to add this here incase anyone else is interested.
Here's how I found to add an icon to a Windows executable created with PerlBin. Note: uses Microsofts "RC" resource compiler.
1. Copy the icon file into the PerlBin folder. (eg. example.ico)
2. Create a PerlBin.rc file (resource script) in the PerlBin folder:
#define IDI_ICON1 101
IDI_ICON1 ICON DISCARDABLE "example.ico"
3. Edited these changes to "genperlbin" where they fit:
system "RC -r PerlBin.rc";
system "$Config{cc} ".ccopts()." PerlBin.c";
system "$Config{ld} ".ldopts()."PerlBin.res PerlBin$Config{obj_ext}";
4. In the PerlBin folder:
Run: perl makefile.pl
Run: nmake install
6. perltobin -o c:\temp hello.pl
hello.exe should now have an icon embedded into it
Crazy, huh?