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?