Esta pergunta é muito semelhante a esta aqui perguntada no Ask Ubuntu: Erro 255 ao tentar instalar o openssl-1.0.1g a partir da fonte
O problema que eu estava tendo, de acordo com essa pergunta bem como um problema arquivado no GitHub (vinculado a da pergunta anterior) é que a versão Perl em sistemas mais novos quebra a compatibilidade com a configuração de construção de documentação antiga do OpenSSL.
A correção mais fácil é construir o OpenSSL sem a documentação correspondente, com o seguinte comando no lugar de "checkinstall":
make install_sw
A única outra opção (mais difícil) é (tentar) aplicar este patch: link
(Note que o patch foi desenvolvido para o OpenSSL 1.0.1g, e não para a minha versão, OpenSSL 0.9.8za - Eu não testei, então eu não garanto que ele funcionará. Minha solução foi apenas para compilar sem documentação, pelos links acima)