Actually, two satellites have already been launched: GIOVE-A and GIOVE-B [1].

And now, things should go pretty quickly, we probalby are 2-3 years away from having a decent fleet flying. Although I can't find a source for it now that I need it...

[1] http://en.wikipedia.org/wiki/Galileo_(satellite_navigation)#...