I ran into this problem recently, certificates were verifying ok but were revoked somewhere along the line. I wanted to check against the CRL but it's a somewhat undocumented feature (fixed in openssl 1.0.2). The -crl_check option checks your cert against the CRL listed in the certificate, but only if that is listed and accessible remotely.
To get the crl_check to work, append the CRL to your CA and then specify the -CAfile option to whatever openssl command you are using (I used s_client and verify successfully).
$ cat /etc/puppetlabs/puppet/ssl/ca/ca_crt.pem /etc/puppetlabs/puppet/ssl/ca/ca_crl.pem > /tmp/ca_combined.pem
$ openssl verify -crl_check -CAfile /tmp/ca_combined.pem /tmp/yourface.pem
/tmp/yourface.pem: CN = yourface.localdomain
error 23 at 0 depth lookup:certificate revoked
$ openssl verify -CAfile /tmp/ca_combined.pem /tmp/yourface.pem
/tmp/yourface.pem: OK
Without the -crl_check, the certificate comes back valid.
(Puppet did tell me that the certificate was revoked, but I didn't believe it, had to verify with OpenSSL, if OpenSSL says it's revoked, I'll believe it.)