Domains should not go down if you have the old server and new server online. Once the change is completed sites should resolve from the new server. If you are getting address not found probably its a issue with DNS. Check the DNS report for the domain ( http://dnsreport.com/ and see what errors it represents.
Well, if you want to not have downtime, and have access to the servers ( root or reseller to edit the DNS ) edit the old servers DNS to point to the new location, and it will keep your site online until the DNS is fully switched to the new server.
If I move my website from one server to another, then change the DNS host records to the new IPs none of the websites should go down right?
It should either show the old server or the new one. I'm having a problem where it says address not found as if the domain doesn't exist.
When you say you're changing the DNS host entries for a domain your referring to the "Hosts" associated with a domain and not the nameservers, correct?
E.g., you had ns1.yourdomain.com @ 22.214.171.124 and you’re changing the IP host address for ns1.yourdomain.com to 126.96.36.199.
If the answer is yes and you keep both nameserver's up during the propagation period then you should have no downtime. If you are seeing downtime then I would check to see which nameserver you're using and verify that it's functioning properly and the records are correct.