Windows sometimes behaves a bit strangely with directories. Are you sure that it doesn't find perl.exe and not just misinterpret the parameter? I sometimes had problems with that; it all worked when I used C:\data> perl "C:\perl\test.pl".
Otherwise you should, as suggested, add the directory C:\Perl\bin to your path by entering the following in the command prompt: C:\data> PATH "C:\Perl\bin"; %PATH%