Be sure to pay attention to the user cron is running as. I ran into similarly bizarre behavior with a CGI I wrote when I realized my "at" command, executed from within it, was running as "nobody" and didn't have access to what it needed. Not the same but similar.

You could also try spawning a bash shell and running it from within that, instead of directly, ie.

bash myperlscript.pl

instead of just:

myperlscript.pl

Also check /var/log/cron for errors.