Default Naviation Issues after KitKat Upgrade

I am on E980 ATT, recently updated to KitKat 4.4.2, official upgrade.

I notice, my location is no longer accurate in the maps app and the "navigate" feature does not work, since my location never really gets pin pointed.

I have checked the "high accuracy" setting in the location settings. I have also cleared "Maps" data as well as uninstalled Maps updates. GPS tools app, also keeps saying "Trying to establish location..." or something of that sort.

Any thoughts?