Just an update, first try just the GPS Test app before using GPSCLRX.
I got a new warranty phone recently, same crap, GPS (Maps, etc.) wouldn't work. I tried the GPS Test app and that got it going. So try that first before using GPSCLRX.
I will update the OP now with this info.
Previous devices: Samsung Galaxy Indulge, LG Connect