Sometimes the mod_perl.so Apache module doesn't like some other compiled C Perl modules (like Template or parts of DBI).
Your best bet is to re-install Template from source. If CPAN tells you that "Template is up to date" just download it manually via
and unzip/install by hand. That should take care of the problem.