I'm not going to get into the WHYs but just wanted to go over the HOWs.
These steps worked for me (debian machine). I had a perfectly configured vps and didn't want to go through it all over again at the new vps provider.
1. create a backup of existing vps
2. order vps at vpsland (wait 24-48 hours)
3. wget backup of vps to new vpsland vps (you can hand craft the url to download your vps backup file so that you don't have to download to your pc then upload from your pc)
4. kindly ask vpsland support to create vps with backup image (wait 6 hours)
5. ssh into your new vps (make sure everything works)
6. change dns settings
You could (maybe) combine steps 2,3,4 into one so that vpsland doesn't create a fresh vps only to replace it with your backup.
1. my firewall script referenced specific ip addresses so I had to connect to the console and manipulate them.
Um... Rsync copies EVERYTHING, even preserve the dates of files and permissions. For Debian, only a few files to modify for changing IP's: /etc/hosts and /etc/network/interfaces. And of course, your firewall.