I don't think it's iOS4
I noticed this happening even before I upgraded my 3G to iOS4. I used to have a handful of cities, but when I tried to add new ones, it would just take me back to my iPhone home screen. I don't recall if I entered any new cities after the last app update, so it could have happened then.
I only noticed this about 3 weeks ago. But, it is consistent, and it has happened on both my 3G and 4, and with iOS 3 and iOS 4.
Thinking I had somehow corrupted my software, I deleted it from my phone and reloaded it over the air. I also removed all of my saved cities thinking that could have been the issue. Nope. Now I have an app with no saved cities. As one of the previous posters mentioned, I can do a GPS search and find my current city, but as soon as I close the app, it's lost.
It's a shame too. I used to prefer this app to Weather Channel.