Some things I would try (I don't use a Mac so can't test):

1. Spawn bash explicitly (the default shell might not be getting all your environment variables):

# Not sure how quoting should work here, so fix if needed
do shell script "bash -c /Users/stevied/bin/clean_desktop.pl"
[download]

2. Create a wrapper (e.g., clean_desktop.sh) which force-sets up perlbrew:

#!/bin/bash
perlbrew use perl-5.16.0   # or whatever version/folder you are using
/Users/stevied/bin/clean_desktop.pl
[download]

Then call the wrapper

do shell script "/Users/stevied/bin/clean_desktop.sh"
[download]