I had the same issue.
Reestablished the trusts and checked all OK.

The only thing i did differentis, replaced the blank password with
some text password and its went smooth.

Make sure that you log off and log back on after changing the password
and then re establish the trust on both sides.
Make enterprise admin from Windows 2000/2003 domain member of the
Administrators group om winnt4.

I hope this will fix the issue

Cheers
DAV