Debian -> Ubuntu: can no longer send mail via Gmail

[Martin Christensen]

I'm at the end of my rope here...

Since I changed from (a somewhat customised) Debian to Ubuntu (Dapper
Drake, no customisations), I find that I can no longer send mail via
Gmail from Gnus. I've been trawling the web and usenet for a solution,
but my configuration seems to be in order.

I've fetched the latest smtpmail.el and starttls.el from Emacs and
Gnus CVS respectively, which I load from my .gnus.el. From what I can
see, I also have the required binaries on my system:

% which starttls gnutls-cli
/usr/bin/starttls
/usr/bin/gnutls-cli

Here's the relevant part of my .gnus.el configuration:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Send mail via Gmail's SMTP using TLS.
(load "~/.elisp/starttls.el")
(load "~/.elisp/smtpmail.el")
(setq message-send-mail-function 'smtpmail-send-it
      smtpmail-starttls-credentials '(("smtp.gmail.com" 587 nil nil))
      smtpmail-auth-credentials '(("smtp.gmail.com" 587
                                   "martin.sand.christensen@gmail.com" nil))
      smtpmail-default-smtp-server "smtp.gmail.com"
      smtpmail-smtp-server "smtp.gmail.com"
      smtpmail-smtp-service 587)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

When I do a (setq smtpmail-debug-info t), I get the following trace:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
220 mx.gmail.com ESMTP d2sm27310nfe^M
EHLO fangorn.rev.stofanet.dk^M
250-mx.gmail.com at your service, [212.10.154.245]^M
250-SIZE 20971520^M
250-8BITMIME^M
250-STARTTLS^M
250 ENHANCEDSTATUSCODES^M
MAIL FROM:<martin.sand.christensen@gmail.com> SIZE=402^M
530 5.7.0 Must issue a STARTTLS command first d2sm27310nfe^M
QUIT^M
221 2.0.0 mx.gmail.com closing connection d2sm27310nfe^M
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Can anyone point me in the right direction? I have absolutely no idea
what to try? My configuration seems to be right out of the book, so
obviously I'm very puzzled, and have been for quite a while now.

Martin