Generally, changing the DNS nameservers takes longer to propagate than editing individual records within the DNS. Editing or adding a TXT or an MX record might take effect in lookups within several minutes.
If you are editing DNS nameservers, you should allow 24 to 72 hours for the updated information to take effect across the internet. In some cases, depending on ISPs and the rate of propagation, DNS changes may start to take effect within a couple of hours.
To be safe, editing the MX record and switching the email from one service provider to another should be coordinated at or near the end of business day or over the weekend.