The more I think about this topic, the more I think the first task at hand is to implement secure, private messaging...the nature of any messages (payment requests or otherwise) sent between wallets is such that it needs to be secured. And the great thing is that it's easy to do and you don't need to solve the PKI problem. Have the wallet maintain one or more ECC key pairs for the purposes of signing and encrypting messages. Allow these to be shared between wallets, or exported/imported, etc. You can punt on the whole topic of verifying the others' public keys using PKI (I mean, people use bitcoin addresses today without the use of any formal or explicit PKI to verify them...people will make do without it for communications keys just fine...and they can always use PGP or other PKI if they feel the need...most people would just pick up the phone to verify a friend's public key)...this also doesn't preclude the use of X.509 for the merchant/customer scenario...
For a payment protocol, you could do something like this: use https & ssl certificates/CAs as one method of obtaining an ECC public key...pki_type could be "https" and pki_bytes could be a url for the https location to download the ECC public key. The software would reject (or warn) if the SSL certificate isn't considered valid by the normal CA validation process. The wallet would not necessarily need to permanently store ECC public keys obtained in this manner. This approach doesn't require people to obtain new certificates just for bitcoin.
In fact, there would be very little difference to the proposed payments protocol if this approach were taken...instead of using X.509 directly for signing and encrypting messages, you are using it for signing and encrypting the ECC public key exchange. And this allows people that don't have web servers or SSL certificates to exchange their ECC public keys by other means and be able to use this payment protocol as well as any others that one could imagine. So, I actually think this is a better way of keeping PKI out of the scope of the proposal.
Payment requests are just one kind of messaging between wallets. I've also mentioned the "cheques" feature. I'm sure there are many more possibilities. Having a uniform method of securing messages sent between wallets (that doesn't depend on external tools) would be a great step forward IMO.