Between IP Address, DNS and location changes, thats going to be tough not to disrupt services.
How many servers are we talking about?
If we are only talking about a small number of servers, you could always setup a temporary dedicated server for every colocated server, then move everything to the dedicated servers while the move is taking place. The only problem with that is you are moving having to move data from server to server twice, which leaves open the opportunity for failures.
The other way would be to just "bite the bullet" and have the customer shut down his equipment, pack it up and overnight for earliest possible delivery time at your location.
Hosting&COLO.COM -- Toll Free: (888) 473-1831 Affordable colocation in Los Angeles. Yes, we have Mzima Bandwidth!
"If you quit before you've given it 100% you will be very disappointed in yourself for the rest of your life."
We had to do this once moving servers from the west coast to the east coast. It took about 2 months to do it. What we did was buy some new hardware at the newlocation and transfer the servers data over the net. After moving 8 to the new servers we took the 8 old ones and shipped them to the new location and repeat the process of moving the data and the servers every week. We could do this since 90% of the servers were the same configs. Ended up with extra servers in the end, but we just filled those with new clients.
Your first step should be getting on the phone with the new DC and seeing what your options are. Some places I have known will set up temp machines at the new location for you so the easiest thing to do would be buy a couple hard drives, Have DC #1 clone each machine then just ship the drives to the new location to be put in the temp machines. Once your equipment arrives pull the plug on the temps and fire up yours.
For the DC it is not a big deal since most likely they have extra equipment sitting around anyway and you will only be using it for a few days..