Having the same issue here too... for a NIS (yp) binding of Lion. I could not login for network accounts, either graphical or via ssh.
It seems to be perfectly connected to the servers, can retrieve all NIS maps on the command line....
but I could not browse the same maps via the (new?!) directory editor in the directory utility at the same time....
Specified in the next step besides only a (search) domain the IP/domain name of the server itself too.
I am not sure if that helped, but it brought up at least ssh login.
For the loginwindow itself I experienced a more erratic behaviour... tried to login 2-3times and it failed, but worked then the next time and so on.... maybe some delays or whatever before Lion updates his database...