I felt that your question was really valuable so I also turned it into a FAQ
http://community.auth0.com/t/can-i-change-from-one-custom-domain-to-another-without-experiencing-downtime/32494
Thank you for your help with this. Hopefully this is something we can get corrected in the future!