Ok posting this for future referencein case anyone else has this problem.
Turns out I made a mistake somewhere along the line of keys and certs, and I had a mismatch. I found this command that you can use to test your key/cert and it gives more details on what is wrong if it fails:
openssl s_client -connect gateway.sandbox.push.apple.com:2195 -cert cert.pem -key key.pem
That commands told me I had a mismatch. I went through the whole process again and now it works.