DNS propagation depends on a couple factors. 1. How long your TTL is That TTL stands for "Time To Live". TTL refers to the capability of DNS server to cache DNS records. 2. How long and many DNS servers have their TTL set at and at what interval their cache expires. This can be around 24 hours or more. It usually starts at around 8 hours, given the default TTL is typicall 86400 seconds (or 8 hours). I typically suggest to people that if you are going to make any changes to your DNS zone file that you first set your TTL to 300 seconds or 5 minutes about a week or so prior to making these changes. This way when you make those changes they will appear almost instaneously.
86400 seconds is 24 hours, not 8. Anyway, all you have to do is get on your DNS server ${TTL} seconds before you want to make a change, set the TTL to 0 (unless you are a high-traffic site and don't think your DNS servers can handle it, in which case use 60 seconds or something), then wait out your original TTL, and then make the change. Then bump the TTL back up. If your secondaries update slowly rather than responding to NOTIFY then you'll have to factor that time in as well. People who use services like everydns may be in this position. I normally use djbdns with rsync to copy the data.cdb file so my secondaries all update instantly.
Doh, no idea why I put 8 in there.. Ooops.. must have mean 24 / 48 or something... Anyway, the only reason I suggest 300 is in case you do have a busy and forget. I've got some clients that have chosen to remain at 300 since they make so many changes on a regular basis.