I'm seeing the exact same behavior in my environment (NT4 PDC, not AD). I had to downgrade samba get systems working again. The full error message is: "The trust relationship between this workstation and the primary domain failed". Did you have any luck finding a solution?