I've had the same problem with vista before but it turned out to be a firewall config issue. I tried adding the weather gadget before replying and even changed different cities, no problem with me.
I'd be very interested to know what's causing this to malfunction. Please let us know if you've figured it out.
Oh, have you tried disabling anti-virus and anti-malware programs too? Just an after thought