I had a similar problem, where i could connect, control, observe, pretty much get full functionality from ARD on both client and admin computers....
...then i started to use the Mac OS X firewall to be more secure when online ec and suddenly i could not connect to, control, observe my admin computer from any clients! the only way i could gain access from the client would be to turn off the firewall in the admin's system preferences!
After reading this forum i decided to have a closer look at the port configuration on my admin computer.
In 'sharing' in sytem preferences in the firewall tab i double clicked the 'Apple Remote Desktop' box to see which ports it actually allowed... the result being TCP and UDP ports 3238...
When i checked the same on my client iBook the ports that the setting allowed were TCP/UDP 3238 AND TCP/UDP 5900!
So i created a new firewall rule on the admin computer entitled "ARD" and allowed ports TCP/UDP 5900 and voila i can now connect to the admin computer with the client without any problems!
Hope this helps, i know it has probably been said somewhere here but i felt this explanation may help those unfamiliar with the process!
G5 iMac 1.8 GHz, G4 iBook 1 GHz, MacBook Pro 15" Mac OS X (10.4.8)