Best Practices in Speeding-up DNS Propagation [duplicate]

DNS records doesn't propagate in the sense that they aren't "pushed" from your server to other resolvers. What actually happens is that when other DNS servers look up your domain, they cache the record for X seconds so that they don't have to do another lookup for subsequent requests. X seconds should be determined by the TTL value on the record when it was retrieved from your name server. If you've already changed the address there's nothing you can do but sit and wait. If you had planned this in advance, you could have lowered the TTL value.

Some larger DNS resolvers cache longer than the TTL, which is a violation of the relevant RFCs (but they don't care). If you can track this issue down to a few name servers, you can email the operators and ask them to invalidate the cache for your zone so that they'll stop using the cached (old) record.

Honestly, though, unless this goes on for an extended period of time, it's probably just as well that you sit tight and wait and plan a better migration for next time, since the damage is already done.

Apart from ensuring that you pre-publish with a low TTL as suggested by the other answers, also ensure that your old name servers are either a) turned off, or b) serving the new zone file.

The reasons why are explained in my answer to this question, but the short version is - some resolvers will continue to query the old name servers, and won't notice that the parent zone has changed.

Are there any best practices when it comes to changing nameservers to minimize this problem?

As MarkM already said - set default TTL to small value. Best practice is "Think forward", i.e - set small TTL before time of change, wait while old records will expire, after it change RR data.