I'm doing a Samba upgrade from version 3.0.23d (with passdb backend = ldapsam) to Samba 3.5.6 but I'm experiencing this problem: if I do "net rpc trustdom list" on version 3.5.3 I can correctly see a domain in TRUSTING domain list. If I upgrade to 3.5.4 or newer version, in the output of "net rpc trustdom list" the TRUSTING domain list is "none".
I have seen working trust setups since then. AFAIR a samba schema update was done in the meantime, you might miss this...