I found out that the 2 Domains seem to have to Trust each other for the LogonUser api to work.
If you found different, please reply