Win98 clients slowed after switching ISP

Hello,
I have an office with an ISP in the same building. We recently switched from an ADSL service to the local ISP. We are now on a subnet of thier newtwork.
Since they came in and made the TCP/IP address changes (gateway, dns, client and server addresses), all the Win89se clients have slowed accessing server shares. The Win2k clinets and Win2k Adv. Server are fine.
These 98 clients seem most slow in the first hour or two of the day and speed up as they go along. The ISP suggestedimplementing the WINS server and configuring the 98 clients for it. Is this a likely sollution?
If so… Do the Win2k clients need to be configured too?
IF not… What else could be the problem?