I had this problem running Windows Servers ever since. Some clients take a unreasonable long time to logon. It seems that the delay comes from loading the user profiles. I use roaming profiles which are shared on the server and are being named User$. Most clients work just fine but some take minutes until they log on. After that they work fine.
No problems reported in the Event Log, no network problems, all drives connected, Exchange server works fine, no problems at all. Same thing occurs on the same clients when logging off.