Moving servers – any special issues?

We have just moved our site from one server to another. Since the move we are experiencing a long delay (up to 60 seconds) between a user clicking on “place order” and the confirmation screen being displayed.
Support services at the new server have put through test orders but cannot replicate the delay, our customers are getting it though.
Are there any issues that I should look at – could it be related to permalinks for example?

Dennis