David,
When doing the local install, are you directly on the remote server? I've seen issues when coming in via Terminal services or RDP. If the server is not a domain controller, log in as a local admin instead of domain admin, to help eliminate any GPO issues. Check for any 3rd-party apps or services that may be causing a conflict as well. You may wish to run DCOMCNFG and check permissions on the remote server as well.
I know all of these steps seem pretty simlistic, but as you know, the Remote Agent installation itself is very straightforward. When it fails, there aren't a lot of possible suspects to investigate.
Greg