Today, I found the same problem on a client's Desktop G4 and became determined to find the answer. After all other attempts were exhausted, I repaired permissions (via Disk Utilities). It did not seem to help until I rebooted. At that point, all worked fine, as it had prior to the problem.
I then came home and tried the same two steps on my PBG4 (repair permissions and reboot), and it was fixed as well. Some will say that this should have been obvious. It was not, to me, and it may not be obvious to others - thus the hint.
[robg adds: I wouldn't have thought to use permissions repair to fix a remote login glitch, so hopefully others will consider this useful.]

