Just to be clear, you're certain you have the perl-suidperl package installed?
Code:
$ rpm -q perl-suidperl
If so, create a test script that is suid:
Code:
$ cat > xx
#!/usr/bin/perl
print "testing.\n";
^D [ctrl-D to finish the script]
$ chmod a+rx xx [Now make the script executable, owned by root, and setuid]
$ sudo chown root xx
$ sudo chmod u+s xx
Test it like this:
This works for me (on FC2, but should work fine on FC1). Without the perl-suidperl package installed, running the test script will give the "Can't do setuid" error.
qmail itself I know nothing about. But if the above test doesn't work, then something besides qmail is screwed up.