I have successfully upgraded a couple of my CentOS 3.x server to the latest 4.x server by replacing them and using cPanel's multiple account transfer feature.
Get the new server hardware together, install the O/S
This worked best for me when I had two NIC's in the servers, the REAL IP NIC and "fake" IP NIC. Configure the new server with the same hostname as the other one, and only setup the "fake" IP network card so you have Internet access.
Get your cPanel trial certificate for the "real" IP of your fake network, i.e. your firewall's reall IP address.
Install cPanel.
Secure your server.
Check for any other differences, extra perl modules, other scripts installed outside cPanel, Zend etc.
Make sure you have at least the latest cPanel stable version installed on the old server.
Unplug the REAL IP NIC on the old server. This will keep any dynamic content form being updated during the transfer.
I killed Exim and Apache and the cPanel monitor that automatically restarts those if they fail, chkservd.
Now log into the new server's WHM, go to the Multiple Account Functions and do the transfer multiple accounts.
Use the "Fake" IP of the old server to connect and list the accounts to transfer. Select the accounts to transfer and click the button. Whatever you do, don't close that window or navigate away from that page in that window. The copy process will continue even if there's no browser to show you the status, so you'll never know when it's complete or what was not copied successfully.
After that's done, you will want to make any neccessary changes to /etc/localdomains to match the old server. You will also want to make sure the DNS zones that had any manual or custom changes are also done on the new server. Those changes don't copy to the new one.
Once you've got that done, you should be able to plug the REAL IP nic in on the new server, and your sites should work as if nothing changed...
Of course we all know that nothing is 100%, so be prepared to drop everything and fix some stuff. There's always risks the upgrade will bring to your customers code that you have no knowledge of. I usually give them a week or two notice if possible to let me know of any problems they might have and also let them schedule time to make fixes once the move is complete.
Don't forget to reconfigure your backups on the new server.
Hope this helped you.
Chuck