This is surprising. What was the TLD for your name? And can you share your SOA config for your zone? (don't need the names, I'm curious about the TTLs in all the SOA fields)
Most TLDs serve glue records with 1-3 day ttls. It's not surprising to me that some servers had the old glue cached (well, I'm assuming they've got traffic... I would be surprised if my domains' glue were cached anywhere of note)
If you can configure your old nameservers to serve the new NS records, sometimes that's helpful.
I was thinking that maybe you had a large TTL for either the SOA or the minimum TTL field, but both of those are pretty reasonable at 5 minutes and 1 minute.
If you can configure your old nameservers to serve the new NS records, sometimes that's helpful.