The hostname utility was removed in net-tools 1.60.20110819cvs-1. The inetutils package, which was recently moved into the base group, will provide hostname from now on. Please make sure to install inetutils especially if you have problems with network utilities.
Hostname utility moved from net-tools to inetutils
Oct. 6, 2011 - Eric Bélanger