Takes a lot of time to get a prompt
 

Anyone seen this kind of problem? It doesn't happen with root, and does happen with both NIS and local users

Can you specify more details? ie.: Is NIS on the same machine? My bet is that authentication is passed to another machine wich is either loaded or the network is a bottleneck. Should you specify more details(configuration/log excerpts) I may be at help.

Check the .profile / .bashrc / other files run on start of shell for the user(s) where you have the problem. Look for anything which is not run for the root user, and run it manually, looking for slow performance. You could put this at the top of your ~/.bash_profile to show commands as they are executed:
...and add this at the end of the file:
...and watch to see which command(s) are taking the time.
[edit]You probably want to do the same in all the files which are run when you log in. see the FILES section of the bash manual page for a list of the files[/edit]