one exchange server, one forest, two domains

Ok,
We have jsut added another domain to our forest by way of a two way trust and I want to extend the exchange server to include the new users. Ther seemd to be a pernissions problem with the new domain for exchange server. AD sees the new domain but I cant get exchange to create a mail box for the new users or even send as permisons to existing mail box but i can give them read access???
How do fix this??