Minimizing Downtime When Switching IP Addresses?

GeekTek asks: "As we all know, prices for co-location have plummeted since the height of the dot.com era. We've been shopping around and found a solution that works for us. We have a small setup of about a dozen Debian boxen, a few Windows servers and we run our own name servers (BIND 8.x). Most of our domain names are managed through our OpenSRS account. My concern is switching all of our server's IP addresses. I can not have any down time and I want to minimize the number of trips to the current co-lo (it's >2 hours away). What is the best way to do it? What experiences can you share in similar situations?"