it can depend on your ISP
Basically it depends on the time at which the ISP processed your request. If you are with an ISP that looks after it's own DNS servers, then you'll get the change quicker. It's all down to the frequency of the updates to update top level domains (.com, .co.uk, and so on). I use BT in work, and I think they update their root servers every 4 hours.
Other ISP's will feed their DNS cache from a major telco (e.g BT). They have to pass the update, up the chain of servers before the master servers will replicate back out to the rest of the world. There's very little you can do, apart from sitting and waiting, if you've just missed a DNS update cycle.

We usually leave our DNS changes until a friday afternoon, as it gives the weekend for the changes to propogate out to the interwebs. The alternative is to put a redirect page from the 'old' server, which points them to the IP address of your new server.
(sarcasmo needs more sleep, Tue 8 Sep 2009, 13:26, Reply)