I don't think we need to say this, but do not accept that certificate.
Either something is wrong with your connection and you have a man in the middle, or something went terribly wrong on your browser, or some application server at PayPal was compromised.
Since everything looks normal from here, and the certificate is legitimate, don't trust whatever is on the other side.
Can you download the certificate and share it with us, out of curiosity?
Are you using a proxy somewhere? Even if you think you aren't, can you check your network and browser configuration to find it out? You may have malware installed or are using a rogue proxy.
Since the problem was fixed by changing the DNS server to Google's, I wonder what was your DNS server. It may have suffered a DNS cache poisoning, or RAM problems in the server may have mixed up cache entries. But I suspect the former: maybe your ISP has suffered an attack. The output of the host
or dig
commands, directed at the server, may be useful to debug.
dig www.paypal.com @8.8.8.8
dig www.paypal.com @(your DNS server)
host www.paypal.com 8.8.8.8
host www.paypal.com (your DNS server)
Also: if even your iPhone was having similar problems, the problem is most certainly in your ISP's DNS server. I'm not sure how effective it will be to warn them, but it may be a good idea.