I don't know if this is a useless anecdote or typical, but last night I switched a domain (moveonhotmail.com )from goDaddy to Jodo and this morning moveonhotmail.com was working. Maybe this is a good plan to minimize downtime. (change your nameservers in the evening)
I have similair story. I bought a .co.uk domain from 123reg. When i purchased it said i could not change nameservers within 1st hour. But i tried anyway, as you do, and it let me So changed them. Then tried the website like 2 mins later. And bang, it worked. I thought that there was no way it can have done it. So checked again. And correct. It literally had worked instantly. This was in the evening here in the UK.