The very concept is somewhat nonsensical. Gmail is a big system with many components -- there is no reason that Google would ever need to do a "complete" rewrite. That said, the individual components are frequently rewritten, and it already supports at least 4 completely different interfaces (AJAX, plain HTML, XHTML mobile, Java MIDP mobile, POP3, and probably others that I'm forgetting or can't mention). Adding a new UI for Joel's magical library wouldn't be a big deal.
There are a number of real threats to Gmail. This isn't one of them.
Though if people were really to move towards encrypted mail, it'd threaten the whole webmail industry. It does no good to encrypt your mail if it's then sent in plain text over the web. Even if you used https, it's a little nonsensical to let a third party decrypt your mail and then re-encrypt it for transmission.
That said, I'd bet that this threatens encrypted mail more than webmail. Have consumers ever chosen security over convenience?
I don't know what's going to happen to encrypted mail, but I can answer your last question.
Burned once, consumers will choose security over convenience. They'll even go so far as to choose inconvenience on the assumption that it makes them safer. Witness people's acceptance of inconvenient airport security, even as baggage went on totally unscreened.
By encrypted mail, I meant end to end, pgp style encryption. For this to be of much use, Google (nor anybody else) would not have my private key, so all they see is a wall of random bytes.
The very core of what makes Gmail so enjoyable is that their expertise in free form search allows me to pretty much stop caring about organizing my mail at all. I generally just hit archive, and rely on search to retrieve whatever I may need to later. No web mail client can provide such a service against encrypted mail.
At the same time, it is Google's access to my mails' content that allows them to show me 'relevant' ads. Without this ability, providing Gmail for free will get a lot harder to justify.
In your opinion how easy would google cope with a need for a complete rewrite of Gmail?