No, that doesn't mean that 500 rlogin connections use 65000 ports.
Yes, that *does* mean that those 500 rlogin connections might well be exhausting one or another limited system resource (like, for example, free ephemeral port descriptors).
Your homework assignment is to do some more research to figure out what resource might be the culprit.
Here's one link that may (or may not) be related to your specific problem:
http://linux.about.com/library/cmd/b..._rresvport.htm
<= The problem might have to do with the function "rresvport"; used by "rcmd", which is in turn closely related to "rlogin"
"netstat -a|wc -l", "netstat -a|less", "lsof" and (of course!) "errpt -a|less" are some of the commands that might be useful to you to get more information about the problem.
You can get lsof binaries for AIX here:
http://www.mirrors.wiretapped.net/se.../binaries/aix/
Good luck!
PS:
And by all means, look at your time_wait settings, too!