After I moved to a hosted version of the Chef Server, I started getting this problem with knife:

knife download environments
ERROR: SSL Validation failure connecting to host: chef.yourdomain.com - SSL_connect returned=1 errno=0 state=SSLv3 read server
certificate B: certificate verify failed
ERROR: OpenSSL::SSL::SSLError: SSL_connect returned=1 errno=0 state=SSLv3 read server certificate B: certificate verify
failed

There are a couple of ways to fix this:

The short-term way is to ignore SSL on your knife.rb file with this setting:

ssl_verify_mode :verify_none

The better and more long-term solution is to add this line to the knife.rb file:

trusted_certs_dir        "#{current_dir}/trusted_certs"

And then run:

knife ssl fetch

I then had to ignore the trusted_certs file in my git repo.

Thanks to Matt Stratton and his colleagues at Chef for helping me find the solution.