Are you binding the Mac and PC side with the same name? Sounds like they are stepping on each other's accounts. When you bind a computer, it establishes a trust with a hidden password. If you bind a computer to the domain with the same name (computer account), then it'll reset that password for the new bind and thus break the trust relationship for the old bind. Hope that made sense - I haven't had coffee today.

I'll have to double check the names when I get a chance. I'll let you know if that was it.

Thanks @thoule

The times that we've seen this have been times when the machine doesn't check in to the domain after x amount of days (I think for us, 30?) on the LAN and the domain decides its an inactive object and that trust relationship is broken. If you unbind/rebind it should fix it.

Time may also have something to do with it. Check that both Windows and Mac are doing time against your domain controller.

We have had the same behaviour as @emilykausalik on occassion, machines that are not booted in one OS for more than a month or two often end up unbound when they do.

We see the domain trust break on Windows 7 machines if they run Startup Repair....W7 can trigger Startup Repair on boot after a non-graceful shutdown. We saw that issue frequently until we disabled Startup Repair.