NIS users suddenly can’t login to SSH

I've recently added a new (client) server to my NIS. For a month or so this worked fine, but since today I suddenly can't login through SSH anymore. Some other services (e.g. IMAP) on the same server work fine. The other NIS client seems to work fine.

The SSH session is terminated immediately after successful login:

some.nis.user@nismaster:~$ ssh faultyserv
some.nis.usern@faultyserv's password:
Connection to faultyserv closed by remote host.
Connection to faultyserv closed.

/etc/log/auth.log contains:

Aug 31 12:42:22 faultyserv sshd[27909]: pam_unix(sshd:session): session opened for user some.nis.user by (uid=0)
Aug 31 12:42:22 faultyserv sshd[27909]: fatal: login_get_lastlog: Cannot find account for uid 1234

If I set UseLogin yes in /etc/ssh/sshd_config I can login, but get a weird shell:

I have no name!@faultyserv:~$ pwd
/home/s/some.nis.user
I have no name!@faultyserv:~$ sudo echo
sudo: unknown uid 1234: who are you?
I have no name!@faultyserv:~$ id some.nis.user
uid=1234 gid=1975(some.nis.user) groups=4294967295,2177(somegroup),/*snip a long grouplist*/

I think there is something wrong with the NIS, but have no idea how to fix this, does anyone have an idea?

My /etc/nsswitch.conf contains (among more entries without nis):

passwd:         files nis
group:          files nis
shadow:         files nis
netgroup:       nis