Two things:
1. Check that the DNS settings are correct on any computer that's slow logging on. Logon times of 5 to 25 minutes can be cause by name resolution problems. Your PCs should be using your domain controllers for DNS.
2. Use Group Policy to turn off "fast logon optimization". Counter-intuitive, I know, but we have found you can run into all sorts of problems when machines try to log on before the network is fully ready. Does not increase the overall "time to ready", just moves some delay to before the logon prompt is available.
http://support.microsoft.com/kb/305293In both cases, these steps will probably need to be taken by your domain administrator.