Issue resolved with a simple restart of the phone. My phone is a business as well as personal one so the last time it was restarted was after the last update
Install GPS Status & Toolbox just to be able to see what's happening. (GPS is highly environment-dependent. If you're in a forest or a large city with closely-spaced tall skyscrapers, it won't work well. Not because of Samsung, because of GPS. (Remember, the entire system is designed for vehicles flying above the terrain. All GPS systems, GLONASS, BeiDou, Galileo all use the same concept, so they're all susceptible to those problems.
If not, try this:
Open the Phone, as if you were going to make a phone call and dial - *#9090# -- Diagnostic Configuration (*#197328640# if that doesn't work)
Menu, select Key Input, enter Q
Menu, select Key Input, enter 0000
Wait for the next menu. (It takes a while.)
UMTS->COMMON->NV REBUILD->NV REBUILD->SYSTEM->PROTOCOL->GPS->IMS or, if you don't have UMTS, UE SETTINGS & INFO->SETTING->SYSTEM->NV REBUILD->ALL
If nothing works, you can try to reflash the OS ([Samsung] How to flash Stock ROM via ODIN) Try to get a file with either 4 or 5 separate files - you don't want the CSC file. (CSC_HOME is basically an empty file, but with the carrier (like CSC_ATT), it wipes your data.)
If reflashing the phone doesn't fix it, you need a new motherboard.