Windows Remote Desktop won't "connect in the amount of time allotted"

I'm trying to simply start a remote desktop connection between 2 PCs on a LAN (both running WIndows XP SP3).

The problem is that Remote Desktop won't connect...can't even get a login in screen.
This goes both directions.  I also have a 3rd PC running XP SP2 and can't connect to that PC either.
I get a message box that says:
"This computer can't connect to the remote computer.  The two computers couldn't connect in the amount of time allotted.  Try connecting again.  If the problem  continues, contact your network administrator or technical support."

The PCs are on the same LAN behind a Linksys WRT54GSV4 Router.

I have Remote Desktop enabled on both computers.
I have turned off the Windows Firewall, my installation of Zone Alarm and McAfee Virus Scanner.

The network seems to working just fine.  Both computers can share files with each other.
They can both ping each other, and I can telnet between them.

I verified that the remote desktop service is running by:
1) telnet to port 3389  (it will connect on port 3389...but of course I can't log in)
2) run netstat -a    It shows that port 3389 is open and listening:
        "TCP       brutus:3389            brutus:0            LISTENING"
3) run PortQuery from the remote computer.  It shows that the remote PC can see port 3389 on the host  PC and that it is ready and listening.
"Starting portqry.exe -n 192.168.1.117 -e 3389 -p TCP ...

Querying target system called:
 192.168.1.117

Attempting to resolve IP address to a name...
IP address resolved to CAESAR

querying...

TCP port 3389 (unknown service): LISTENING
portqry.exe -n 192.168.1.117 -e 3389 -p TCP exits with return code 0x00000000."

I'm at a loss.  Everything looks fine...but they just refuse to connect.