One-time login links break on account creation

I am testing a site that I have just upgraded from 6.17 to 6.19, running on Ubuntu 10.04.

When I create a new user, the one-time login link in the account details email does not work - I copy and paste it into the browser but am redirected to the main page of the site, instead of being logged on.

The link in the request new password email DOES let me login with the new user.

All existing users are able to log on normally. Users were reporting sporadic problems like this while the site was running 6.17, but I chalked it up to EBKAC because the vast majority had no problems. Now it is happening with _every_ single user I create.

Investigation already undertaken:

Answers on issues elsewhere (eg http://drupal.org/node/807804) recommend changing the $cookie_domain setting to fix similar one-time login problems. I did not have $cookie_domain set at all. When I set it to ".mydomain.com" just in case, it still did not fix the problem.

One issue (http://drupal.org/node/199151) talks about long strings in emails being truncated by certain email clients; I have checked Lotus Notes 8 and GMail, neither are truncating the login link, but both are having problems.