HOSTEONS.COM allow free OS change/reinstall on all our VPS packages and you even don't need to ask us to change the OS.
Our VPS comes with a VPS Control Panel to reinstall as well as change OS of your VPS, currently we offer following OS:

1) CentOS
2) Fedora
3) Debian
4) Ubuntu
5) Windows 2008  (availalbe on vps3 and above packages)
6) Windows 2012 (availalbe on vps3 and above packages)
7) FreeBSD (we provide ISO for FreeBSD and it can installed over VNC)

Even if you have a orderd a VPS with Linux you can still instant change the OS anytime from the VPS Control panel to Windows as long as your vps package allows it.