The structure of water in the hydration shells of small hydrophobic solutes was investigated through molecular dynamics. The results show that a subset of water molecules in the first hydration shell of a nonpolar solute have a significantly enhanced tetrahedrality and a slightly larger number of hydrogen bonds, relative to the molecules in water at room temperature, consistent with the experimentally observed negative excess entropy and increased heat capacity of hydrophobic solutions at room temperature. This ordering results from the rearrangement of a small number of water molecules near the nonpolar solutes that occupy one to two vertices of the enhanced water tetrahedra. Although this structuring is not nearly like that often associated with a literal interpretation of the term "iceberg" in the Frank and Evans iceberg model, it does support a moderate interpretation of this model. Thus, the tetrahedral orientational order of this ensemble of water molecules is comparable to that of liquid water at similar to 10 degrees C, although not accompanied by the small contraction of the O-O distance observed in cold water. Further, we show that the structural changes of water in the vicinity of small nonpolar solutes cannot be inferred from the water radial distribution functions, explaining why this increased ordering is not observed through neutron diffraction experiments. The present results restore a molecular view where the slower translational and reorientational dynamics of water near hydrophobic groups has a structural equivalent resembling water at low temperatures.