You are probably seeing cached records. when the end user needs a DNS record, he asks his recursive DNS server (usally at the ISP). If the ISP's DNS does not have the record, it queries the root servers to find the appropriate DNS server, then the DNS server for the record.
It then adds this record to the cache. The time cached is supposed to be goverened by the TTL (time to live) for the DNS record. There are always some misbehaving ISP DNS servers (I've seen AOL cache for days, despite a 1-hour TTL), but for the most part, you should see all DNS records update within the TTL.
In the future, when the switchover is approaching, you can shorten the TTL on the old server to reduce the time to switch to the new servers.
Added: As David pointed out, update your serial (version) number of your record. Some DNS servers don't update properly if the serial does not update. Also, it can help you track down problems with propagation.