There should no problems to change your host-name at your web-server.
Normally can this be done by the Plesk Management module at your server settings and/or Virtuozzo. (I prefer Virtuozzo)
Also you have to create/change DNS records for your primary domain of that host-name.
- Create a A DNS record. Pointing from newhost.mydomain.com to IP adress.
- Create a C NAME record. Pointing from oldhost.mydomain.com to newhost.mydomain.com.