It'd be strange and unusual, but it sounds a lot like CGI.pm isn't installed, or isn't in your path.