Because I wanted to be able to give Windows 7 machines access to our domain controller, I needed to upgrade samba to 3.4 from lenny-backports. Because the database backend changed, a consequence of this was that the user database was empty; it didn’t migrate it.

pdbedit has an option to import the old smbpasswd file: 

pdbedit -i smbpasswd:/etc/samba/smbpasswd

That should take care of it. I didn’t test it this way though, because I already fiddled with the user database by creating new users by hand. I imported one user with which I still had problems correctly this way, but I don’t know if importing this database from the start would have prevented all my errors.