Har! Besides the certificate problems, are there other problems with PEM that have prevented its adoption?

That's it. PEM "blew it" by relying on Internet-wide X.500/X.509 deployments. They're now looking at self-signed certificates as a transition aide to work around the adoption problems, particular in face of the pressure brought by the success of PGP. /r$