El Galaxy nexus se puede liberar sin pagar con la app FuckDocomo, la ultima version creo que era (o la que yo use) la 3.1.
Siendo root, claro. Instalas la app, le das a liberar... y tachan, te lo libera.
Pero si, a mi me paso como a ti... me compre el GNex creyendo que era libre, porque venia de un Nexus One (ambos de vodafone) y si que era libre de fabrica...