If you are talking about a Nuvi that you already own, I would say the answer is never, to add a new satellite constellation such as Galileo, Glonass, Beidou etc. to a unit that only has GPS, would not be just a software / firmware upgrade, it would require new hardware i.e. a different GNSS receiver chip.
There are products currently available that receive GPS, Glonass and Beidou, I have a Samsung Tablet that does this (although I don't know of any Nuvis that do this), there are newer GNSS chips available that will receive GPS, Glonass, Beidou, Galileo, QZSS (Japan only) etc on both L1 and L5, for example the Broadcom 47755, this chip would require only software updates for Galileo because the hardware is already in place, however it may quite a long time before a Nuvi, Drive or Drivesmart is sold that do what you ask