Are you using the default $LANG setting? Do this:
If it contains "utf8", then that's probably the problem. Change it so it does not contain "utf8" (see RedHatMalformedUtf8), and the performance issues will clear up.
Perl 5.8 uses Unicode character sets internally in this situation, and unfortunately, this greatly hurts performance of all Perl code which operates heavily on strings (like SpamAssassin).