Yesterday I couldn't get a lock and updated the AGPS data using GPS toolbox and the lock came within seconds. I set it to download AGPS data automatically every day. Today it locked right away. I will keep testing, but it does seem to help.
As I understand it, the AGPS data helps it locate satellites faster. Maybe the GPS chip works, but isn't the greatest and needs the updated GPS data.
According to Wikipedia:
Assisted GPS, generally abbreviated as A-GPS or aGPS, is a system which can, under certain conditions, improve the startup performance, or time-to-first-fix (TTFF) of a GPS satellite-based positioning system