Speed is a know issue right now, especially from countries other than the US. However, the host we're with is moving to a new data center right now, and should be finished by the end of the year/early january. There, the server has tons more of possibilities to send and recive data from all over the world (everything from OC192 down to OC3 lines is there).
On the other hand, this server has tons of advantages for us. For example, it's now possible to create mails, subdomains, FTP logins and much more within minutes - compared to days and even weeks before, where we had to request them. Furthermore, we aren't using one server with several other pages together any more, where one slowdown brings down the whole net.
I think the last issues will be resolved soon, and belive me, I'm more than happy with the new server.