One problem I have run into lately when using ARD 3.51 on a 10.6.8 Server Mac Pro to access 10.6.8 or 10.7.2 systems is that ARD will intermitnely fail to refresh the ststus. Using Refresh on the File menu (top of screen) will update the task status back to available and allow operations to continue. There are even times when the indicated status is off-line but I can still control the remote computer and other times when nothing can be done till the status is refreshed. I don't have a clue as to why this is happening.
One other thing you might try is to delete the affected computers from the All Computers list and then re-scan and install them back into ARD. One cause I have run into for this is when DHCP assigns an IP address to a system but that IP has already been used by a different system and is still carried as being used by the now disconnected system when shown in the All Computers list.