Well, in fact it doesnt work here either.
I tried your setup, with a Windows 2000 domain, and an Ubuntu Linux as a client. I'm working at it. I will come back asap with the fix. Fingers crossed.
Edit: This is the log.smbd output when I try to access the share (and got the user/pass request on windows side)
Failed to verify incoming ticket!
I remember have seen something like spnego and didn't know a lot about it times ago. I'm checking krb5.conf & googling to find out.