Turns out Thunderbird is broken.  For some reason TLS does not work in the current Thunderbird either with our mail server or Googles IMAP, but STARTTLS does.  Investigating further.