Ubuntu Servers :: Domain Workstation Cannot SSH To Other One

I have a truly freakish thing happening here. First I'll start with a general map:
Workstation A (10.10.0.100) - Ubuntu 10.10 joined to mydomain.local via likewise-open
Workstation B (10.10.0.101) - Ubuntu 10.10 joined to mydomain.local via likewise-open
Workstation C (10.10.0.102) - Ubuntu 10.10 NOT joined to any domain
Server A (10.10.0.1) - Windows 2003 AD Server on mydomain.local
Server B (10.20.0.1) - Ubuntu 10.10 joined to otherdomain.remote

As you can see I've successfully installed likewise and I've been able to get SUCCESS notifications from the join. I've been able to log in locally with a domain user and use a domain user password. I've also added a special Group in AD for linuxadmins and then added that to my /etc/sudoers file so I can sudo from a Domain Account. Great right? I'm slowly replacing Windows. But there's a hitch:

I can't SSH from machine to machine! but it's still not quite that simple.
I can SSH from Workstation A to Workstation C as a Domain User.
I can SSH(Putty) from Server A to Workstation A and B as a Domain User.
I can SSH from Server B to Workstation C as an alternate Domain User.
I can't SSH from Workstation A to Workstation B as a Domain User.
I can SSH from Workstation A to Workstation B as a Local User.
I can SSH from Workstation B to Workstation A as a Local User.
I can't SSH from Workstation B to Workstation A as a Domain User.

Complicated enough for you? The simple version is that if it's joined to the domain I can't ssh into another machine that's also joined to the domain while I'm a domain user. But give me a local account and it's as if there's not problem. I tried looking through the logs to find something but wasn't about to find a "sshd" type log. Syslog was completely unhelpful as it doesn't really show anything for the time stamps of my connections. Where does one start troubleshooting this?

I thought it might be a groups thing like the sudoers file, but I don't have an ssh or sshd group. Oh and what does SSH do? What's the error it throws?
Code:
MYDOMAINdomainadmin@workstationa:/$ ssh mydomain\domainadmin@workstationB
The authenticity of host 'WorkstationB (10.10.0.101)' can't be established.
RSA key fingerprint is OB:SC:UR:ED:FR:OM:YO:UF:OR:PR:IV:AC:YR:EA:LL:Y!.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'WorkstationB,10.10.0.101' (RSA) to the list of known hosts.

Here it waits for exactly 120 seconds and then...
Code:
Connection closed by 10.10.0.101
What can I do?