I just upgraded the vserver kernel in my test environment to 2.6.31-vs184.108.40.206.23. After rebooting the machine I recognized that the hostname of the host machine was set to the hostname of the last vserver started. Checking all vservers I found out that all had the same hostname.
A quick google search revealed, that I am not the only one having this problem: linux.derkeiler.com. But the search revealed no solution.
Afterwards I remembered that I masked util-vserver-0.30.216_pre2841 as I described in util-vserver-0.30.216_pre2841 vserver startup fails. So I removed the mask and installed the newer version of util-vserver. Afterwards everything was normal and the vservers, as well as the host machine had the correct hostnames.
It is important to use the version of util-vserver matching the vserver kernel version running. The vserver kernel 2.6.31-vs220.127.116.11.23 seems to work with util-vserver-0.30.216_pre2841 and the vserver-kernel 2.6.28-vserver-18.104.22.168.4 works with util-vserver-0.30.215-r3.