The problem seems to be that update-rc.d orders the init scripts so that
xdm starts before elogind, so waiting for elogind to start before
logging in solves the issue.
Is this something the elogind package can solve? My guess is that's
xdm's (and other dm) duty...