You need to set $File::Find::prune:

    if ($uid < 500){
        print "UID is $uid, skipping $File::Find::dir $_\n";
        $File::Find::prune= 1;
        return;
    }
[download]

This is akin to the -prune flag of find(1). The pod for File::Find only gives one example using $File::Find::prune, unfortunately.