El 'use utf8;' solo sirve para indicar que el propio programa está escrito en utf-8. No influye en la salida de caracteres en utf-8.
La siguiente línea, si suponemos que pertenece a un objeto CGI, lo único que hace es sacar una cabecera HTTP indicando que lo que sigue estará en esa codificación, pero tampoco influye en la salida de caracteres en utf-8.
Es posible que haya ocurrido un cambio de versión de Perl...
Como primera solución (no la he probado), si tienes una versión de CGI moderna, prueba a enviar la cabecera de esta manera:
Using perl Syntax Highlighting
print $q->header(
-type => 'text/html',
-charset => 'utf-8',
);
Coloreado en 0.002 segundos, usando
GeSHi 1.0.8.4
Estaremos enviado la mismas cabeceras, pero además, se estará llamando a la función charset() de CGI, que indica qué codificación queremos en la salida.
¡Ah!, intenta usar una versión de Perl lo más moderna posible.