Connection with hosts drastically slowed - Any ideas??

In the last few weeks the connection to our hosts has been slowed right down to the point that it is nearly impossible to remain connected via Telnet, FTP, ODBC for anything longer than a minute or so, and the sites that we have hosted with them are taking forever to re/load. We have an ISDN connection.

Our user quotas/logfiles/server space are all well within bounds, and there is not too much of a bandwidth load on our server.

Our hosts reckon everything is OK their end although they did have a hardware changeover on their top end servers several weeks ago. (We have a mid-size server) They said to try our ISP as there might be a problem there. Our ISP says all is OK too, so we're stumped.

Access to our server from somewhere other than our offices is fine ( our visitors are not noticing any problem, we hope) and on the flipside, access to any other sites from our offices is up to speed.

So we're a bit stuck on how to find the problem.
Any ideas appreciated.

That could be many possible causes. I'd first see if it's a DNS problem by accessing to your default site via its IP only. Then do a traceroute and see where it gets stuck. You also should ask your ISP to try to access the site for you.
BTW, is it slow initially or after the connection is established or it's fast but can't stay alive and get dropped?

Thanks for replying - I tried Telnet/FTPing using the FQDN's IP address but still had problems maintaining a connection.

I also tried tracert and it seemed to time out on several hops although it got there eventually. There are IP addresses for where it times out - I'll go see who they belong to.

Actually there are no IP addresses for when the tracert command timed out.

Will check immediately before and after timing out.