DNS propagation - why is a subdomain only accessible minutes after it's creation (own nameservers)

My understanding of DNS is that to resolve a url, the process is as follows:

Usually when we contact a DNS server it is not the first time it has received a request for a specific website, they keep the records from previous requests until they expire. The amount of time till expiry (TTL - a value in seconds) varies depending on your settings. If you change you records, the chances are there are plenty of DNS servers out there with these cached records. Once these records expire or the first time the server receives a request for a url it does not know, the DNS server does a 'recursive lookup' in order to get fresh data.

The following is a recursive lookup of a.contoso.com. (Notice the dot at the end which is normally hidden)

The process starts off working backwards, starting with the hidden dot at the end of a URL:

1 - Contact the root name servers (dot servers), their IP addresses are pre-loaded onto DNS servers, these IP's are the same for every server and don't change, they give an IP address for the .COM DNS servers (or whichever TLD you use such as .net)

2 - You then query the .COM DNS for 'contoso' in contoso.com. (this may be where your problem lie if you've changed nameservers)

3 - You then query contoso.com's DNS (your nameservers) for the 'a' in a.contoso.com

ad infinitum ( b.a.contoso.com, 2.ww.c.b.a.contoso.com...)

The process of these recursive lookups replacing stale records is known as propagation.

I would presume your not getting a request sent to your name server because of propagation during a switch-over, your server is not replicating the A record to the nameserver correctly

Domain propagation is only an issue when transferring a domain, not when a new one is created as your not having to deal with out of date records since those records never existed. The request will go straight to the source.