Oliver, an iClarified user, explains the issue, "With cellular data ONLY the IOS 6 the weather app will not update. The local weather section will update randomly. Other cities will NOT update and when trying to add a new city the app won't find any matching cities. I tried that on family members iPhones and co-workers iPhones (4, 4S and 5) all on ATT. iPhones on other carriers did not have any problems."
Users on other forums are experiencing the same problem...
Posting on an Apple's Discussion Boards thread (2) about the issue, K9Lover said, "Just purchased new iPhone 5 today...it is running ios 6.0.2 (the recent software update that was issued only for iPhone 5 users and iPad minis)... Same exact problem exists on the NEW iPhone 5. Native iPhone weather app will not update over the 4G LTE network. It will only update (or let you ADD a city) over WiFi."
Another thread on MacRumors has users reporting the same difficulties and we've also verified the issue with our own devices.
Apple Customer Support is said to have confirmed the problem and passed it to their engineering team for investigation.
Post in the comments and let us know if you've noticed any of the same symptoms.