Por algum motivo, PKG_CONFIG_PATH não continha o caminho certo para o arquivo openssl.pc necessário para o utilitário pkg-config. Eu fiz find / -name 'openssl.pc' e achei em /usr/lib/x86_64-linux-gnu/pkgconfig/ . Esse caminho também foi usado pelo meu outro Ubuntu para ./configure .
Então eu corri ./configure PKG_CONFIG_PATH="/usr/lib/x86_64-linux-gnu/pkgconfig/" e isso funcionou!
Outra coisa, existe outro openssl.pc no meu /usr/local/ssl/lib/pkgconfig/ mas quando tentei usá-lo, o seguinte comando make trava com erros diferentes (como referência desconhecida a função, etc.).