Recent efforts in finding materials suitable for storing hydrogen with large gravimetric density have focused attention on carbon-based nanostructures. Unfortunately, pure carbon nanotubes and fullerenes are unsuitable as hydrogen storage materials because of the weak bonding of the hydrogen molecules to the carbon frame. It has been shown very recently that coating of carbon nanostructures with isolated transition metal atoms such as Sc and Ti can increase the binding energy of hydrogen and lead to high storage capacity (up to 8 wt % hydrogen, which is 1.6 times the U.S. Department of Energy target set for 2005). This prediction has led to a great deal of excitement in the fuel cell community [see The Fuel Cell Review, http://fcr.iop.org/articles/features/2/7/4]. However, this prediction depends on the assumption that the metal atoms coated on the fullerene surface will remain isolated. Using first-principles calculations based on density functional theory, we show that Ti atoms would prefer to cluster on the C60 surface, which can significantly alter the nature of hydrogen bonding, thus affecting not only the amount of stored hydrogen but also their thermodynamics and kinetics.