attempt a traceroute to the server, it could be a number of things from your ISP's route to the server, to the actual hosting company itself. Usually a traceroute will be able to tell you where the connection is slowing down, if you copy and paste the results here, I'm sure we'll be able to help.
Or you could wait about 6 hours, if they are continuing to have problems, it maybe a early indication the hosting isn't for you