Make sure the path that comes through from your HTML::Template generated page is the actual path to the CSS file. Sometimes I have found the developers designing the HTML templates use document relative paths to the CSS file in order to test their design. Once this is used in the CGI scripts via HTML::Template the paths all change. I would view source on your generated page and make sure that is the path you want. If not you will have to change it in your Template file to get it to work. Try making the path root relative, so instead of something like:
That way its the servers problem of finding it and not yours.
Just a thought.