I have found that the widget doesn't update too frequently. Go into the Weather app and manually update it. Thats what I do.

 

Not a problem for me in the UK - updates pretty regularly.

Check to make sure in your settings that you have Location via Wireless Networks ticked?

If this does not work, you could also try ticking the Enable GPS Satellites to help the Location process (though I do not use this).

 

I had the same problem when I first got my Hero. It was 'set up' by the guy at the store and would not change the city no matter where I went or how hard I tried to change it. I ended up caving and reset the phone out of frustration and it worked. I live in a twin city area and now it updates automatically whenever I move between the two. Hope this helps.