Re: Receiving the signal
"Navstar s the name of the American system, not GPS. GLONASS, Navstar and Galileo are all types of GPS."
That's exactly backwards. The American system is explicitly called the Global Positioning System; Navstar was an old name that is no longer used. GPS, GLONASS, Galileo and others are all satellite navigation systems (GNSS is the usual abbreviation for "Global Navigation Satellite System"); only one of them is called GPS.
As for the question about whether you need a new phone, it probably depends on how old your phone is. Galileo and newer GPS satellites are designed to be easily compatible so at least in the future most devices will support both by default. For now, all the separate systems require a separate receiver, so you need to check which ones they can actually use. GLONASS support is fairly common in addition to GPS, and Galileo isn't too unusual, so it's quite possible a current phone will work them all. Beidou and NAVIC are currently only regional, so you're unlikely to find support for them in phones not sold in the relevant regions.