The project has changed somewhat since we posted the outline[1]; basically we're focusing on email only to start (instead of email/IM) and we'll be a service that sits on top of your existing email inbox (instead of a standalone email service). We'll be releasing a [possibly paid] beta by the end of July.
http://geekyschmidt.com/2010/08/28/netcraft-confirms-pgp-ema...
This is not just a first-use problem, either. At least Outlook happily accepts valid-but-different-from-previously-seen certificates, and will encrypt replies to the certificate signing/encrypting the message being replied to. Thus, if I can convince BadCA to give me a certificate for thomas at matasano.com, I can send a mail "hey, $PARTNER, I'm away from my usual devices and I really need the proposal for $BIG_CUSTOMER. Could you send it to me? Please don't forget to encrypt it." Such an e-mail will appear appropriately signed, and I can read any replies $PARTNER sends.
Deploying S/MIME within an organization or within a couple of mutually-trusting organizations works just fine, of course; it's only involving public CA's that causes a problem.
(Or did I miss something?)