Here's how to reproduce the problem :

1. Configure an additional provider in Auth (e.g. LDAP)
2. Create a new user account in People (e.g. John Doe)
3. John receives an email, clicks the link, works in Phabricator, great !
4. ...his session expires...
5. John wants to log in, but is invited to create a new account

Administrative approvals are disabled and registration is not allowed, so basically only administrators create users in our instance.

Looking further in the database, the field phabricator_user.user_externalaccount.userPHID is empty for the John Doe account. I had to manually copy the value from phabricator_user.user.phid as a workaround.

phabricator fea2389066edf3ad0a7547ae12d8e988428a4f5c (Apr 2 2016) 
arcanist    f89f3de65805f7f65c8082ed387e8e2572596f7a (Mar 19 2016) 
phutil      d414e4436e1c8779634458c23ab8880cf613312f (Apr 2 2016)