Whenever someone says "it works fine from the command line but it doesn't work as CGI..." it makes me think of users' permissions. The user executing CGI scripts is oftentimes "apache" or "nobody". When you run the same script from the command line, you're logged in as a user with rights and permissions that are usually quite different from apache/nobody.

Also, I'm guessing you're running the CLI script with the same account you ran the PPM to install Crypt::SSLeay which is different than the account your web browser uses to exectute the script as a CGI.

It may or may not help, but it's something to think about.