sydhe
King of Kongs
I think that the linguistic connections for the name of Eastern Europe's Galicia are semi-tenuous and are mostly adopted in lieu of anything better. The word comes from Halicz/Halych, the name of a reasonably powerful medieval principality in the area. It might've been named for some mysterious Celtic group there, but there's no actual proof of one spending time in the region, and no explanation for why its name would've been given to the area. There are other linguistic arguments for the name, but they're just as dubious.
It would be a relief if it turned out to be a coincidence. There's some dispute over the "Gal" in Portugal, but the Gallaeci lived in what are northwestern Spain (hence the Spanish Galicia) and Northern Portugal, and there were Celts throughout the region.