You are right Jan, though it can take up to 48 hours for your nameservers to become available for a new domain - however it shouldn't really take more than 12. When new nameservers take that long, it's because your registrar does not send the data to the registry very frequently. Some don't, some do.
The registry updates the zone files twice a day. You can tell if your nameservers are listed by the registry by checking the whois at internic.net.
Your registrar needs to send your changes to the registry before the registry updates the zone files in order to start off the process.
This is why some people get confused when it comes to how quickly "their registrar" can update the zone files. The timing of when you define nameservers for your domains and when the zone files are updated can make it seem like it was nearly immediate if your registrar has the registry timing down pat, or that it took half a day or longer
.
If these are new nameservers for a domain, once the registry updates the zone files the domain should then resolve, since nothing has been cached in any ISPs caching DNS resolvers. Once this data has been cached out in the world, changes to your nameservers will require up to 48 hours to be visible (the Time To Live value at the registry for entries in the zone file is 48 hours) and changes to your actually DNS records will take the TTL values from your DNS records to change - if the ISP caching resolvers are playing by the rules.
And that's probably more than you wanted to know
.
-t