troubleshooting really slow login on a (linux) machine

Within the last couple of weeks, any attempt to login to a specific linux server has gotten really slow. Once I've logged in, things appear to run without significant delay, but some other login like activities (like starting a new screen session) are slow.

The machine's been rebooted a couple of times recently and that hasn't helped. , and it doesn't appear to be $PATH search (where $PATH can sometimes include bad NFS mounts), which I've seen historically in our environment. I've also tried completely removing my .profile/.bash*/... type of init files to rule out anything bad there. I also see slow login for at least one other userid on the system.

One thing I've noticed is the following message when trying to exit from a screen terminal:

Utmp slot not found -> not removed

and am wondering if this is related (having a vague recollection that Utmp has something to do with login).

Any idea what that message means, or how to fix it, and if it would be related? Failing that, what sort of problem determination tools are available to investigate what is slowing down this login process?

You probably have a problem with either file:

/var/log/wtmp
/var/run/utmp

The last command may give you strange result. You can use the setutent command to repair it. Or just the simple way:
1. log as root and rename the 2 files.
2. don't log out, for security.
3. log in with whatever user, then log out. The 2 files should be recreated.
4. as root: last should give you a sensible output.
5. if you are sure everything is okay, delete the 2 files

I have had similar issues - in our case we found that there was some old config left over where a name of a system or a DNS server was configured but was not accessible.

Suggestions from me: ensure DNS resolution is working fine on the machine you are connecting to. If you have assigned a hostname to the machine make sure that you edit the /etc/hosts file to at least have a matching entry for the 127.0.0.1 address like this:

127.0.0.1    server-name localhost.localdomain localhost

If you are using static IPs also add:

<static ip>  server-name