Samba in multiple domains problem

Hello all. I'm hoping you can help with a problem I'm having with Samba. I have Samba running on a Solaris host. All of my users authenticate against the same domain, but some of my users are using PCs on a different domain. When the users whose PCs are on a different domain try to connect to my Samba share, their accounts get locked in AD.

This smaller collection of users moved from one of our sites to the main corporate site where their computers are joined to the corporate domain instead of ours. I've had someone test his account on our PCs and theirs and found it only happens when he uses theirs.

Does anyone have any recommendations on a good way to make this work?