Make sure first that you have certificates installed on your Debian in /etc/ssl/certs
.
If not, reinstall them:
sudo apt-get install --reinstall ca-certificates
Since that package does not include root certificates, add:
sudo mkdir /usr/local/share/ca-certificates/cacert.org
sudo wget -P /usr/local/share/ca-certificates/cacert.org http://www.cacert.org/certs/root.crt http://www.cacert.org/certs/class3.crt
sudo update-ca-certificates
Make sure your git does reference those CA:
git config --global http.sslCAinfo /etc/ssl/certs/ca-certificates.crt
Jason C mentions another potential cause (in the comments):
It was the clock. The NTP server was down, the system clock wasn't set properly, I didn't notice or think to check initially, and the incorrect time was causing verification to fail.