When running under Apache with suid scripts, the @INC array does not include the current directory ("."). This breaks all sorts of stuff in semi-spectacular ways. :) I've resovled this by running through all of the scripts and adding "." to the push line in the BEGIN block, as in:
push(@INC, "..", ".")
This behavior is described in perlsec at "Taint mode and @INC". This also explains why setting PERLLIB or PERL5LIB in the Apache config doesn't help. :) I felt that updating the push was the simplest solution to this behavior.