The admin Machine is also on Mtn Lion, so both on 3.6
So, i got it going, here's how i did it:
On the client I had to log in as root and unchecked the Remote Management and re-checked Remote Management.
That must have updated or tweaked the preference, but now it's working properly.
Strange, but that seems to have fixed it..