That sounds like geodecoder problems and really not much of anything you can do about it. Aside from forcing GPS instead of Network locations that is, but who wants to do that.
To be honest though the TouchWiz weather widget was giving me and my girlfriend trouble. For her the widget is frozen at like some random point in time back in December, truth, and it won't update no matter what we do to it.