You don't show us your Perl code, so it's hard to give you concrete advice. Most likely, some quoting is messing your strings up - I recommend a here-document to circumvent all those ugly quotes:

my $shell_code = <<'SHELL';
cleartool lsvob -short | \  
  sort | \  
  sed 's/.*/test -d "&\/." \&\& echoexec cleartool find & -versi +on \
+"lbtype(LABEL1) \&\& !lbtype(LABEL2)\" -print /' | \
  sh
SHELL
warn "Running >>$shell_code<<";
system($shell_code) == 0
    or die "Couldn't launch >>$shell_code<<: $! / $?";
[download]

I'm also not sure about the weirdo quoting going on - I think many of these commands are better done within Perl, but that's hard to say because I don't know what they are supposed to do.