Acontece que openssl verify não permite vários parâmetros -CAfile . Em vez disso, tenho que concatenar root.pem e intermediate.pem em um único arquivo e passar isso como um parâmetro.
$ cat root.pem intermediate.pem > concat.pem
$ openssl verify -CAfile concat.pem john.pem
john.pem: OK