Checkout 1Weather. I love it. The only downside is that Kitkat -- or AT&T, I'm not sure which -- has made it so that ONLY the stock weather will show on your lock screen. Unless you install a new lock screen, which comes with it's own complications (and, no doubt, huge battery usage).
However, you might want to check out the trouble shooting section, because I think I'd read something about your problem. Or google it.
Finally, pretend that your phone is a windows computer and reboot it. That often fixes things.