Hi Mai,
Ok...I'm trying to get this straight here.
1. You have both forests and domains at 2003 Server level
2. You are being denied trust creation based on credentials
Have you checked the security logs on the machines in question?
Sometimes if you configure stricter security settings (like my favorite template hisecws.inf) on one of the machines and not another, the box will reject all non-NTLMv2 traffic. So basically if you're using LANMAN or NTLM it would get denied.
I know this doesn't quite work the way NTLM is supposed to through negotiation, but I've created this issue in my labs a few times and has to do with the security policy of the machine in question.
This link talks about how things may be misconfigured.
http://kb.iu.edu/data/atcd.html
I hope this helps, if I misunderstood the question please let me know where I went wrong.
Jon