I'm having a similar issue, and was able to solve it, strangely enough, by removing the absolute path from the perl command ('C:\Perl\bin\perl' caused a 'Could not start' status in Scheduled Tasks).
Comment on Re: Help! perl in scheduled task doesn't work!
The Task can not be run, because it doesn't find the file 'C:\Perl\perl'. You have either to specify the full file name with the ending '.exe', resulting in 'C:\Perl\perl.exe' or as you did with only 'perl', which will use the PATH Environment and make the full path from it. This solved the problem for me. Thanks.