Terminal Server clients slow to log on

We use Windows 2000 Terminal Services exclusively at our office. We’ve had a lot of hardware changes to the client computers over the past year. All of the original client computers access the log-on screen very quickly, but any of the newly replaced clients (with new installations of TS Client Connection Software) take a very long time to connect with the server and provide the log-on screen. The only difference between fast & slow clients is in the list of DHCP Address Leases. Fast clients have a slightly different icon than the slow clients.