I am doing an upgrade right now to ESX vSphere4, using the Host Update Utility, sure enough it failed (nothing ever works the first time, right?) with this error message Upgrade Package Validation Failed: Unsupported ESX version: esx-4.0.0-1.9-208167-release .
Basically what it is saying to you is that you have to download the matching revision of VMware vSphere Client and Host Update Utility. For the above release you will need the VMware-viclient-all-4.0.0-208111. Once installed you should have no issues!