I had this issue too.
Delete the clock/weather widget.
Uncheck the VZW location and GPS.
Check them again, add the clock/weather widget and update it manually.
I had this problem since day one. After I did the above, it's worked perfectly fine since.