Our data comes from CustomWeather, the same provider a lot of other apps (like Fizz Weather) use. At the moment we only support all the locations they do, though at some point in the future we may consider adding other data sources. What sources do you guys find most reliable for where you live?
As for the icon, we will probably tweak it over time as we play with new ideas. It's good to hear your thoughts on them, as it could drive what we do in the future...but this is not App Icon Idol
(besides like I said those were some of our earliest designs, not the later ones).
Edit: The temperature is pushed every 5 minutes. Turning notifications on for 20 apps causes the same battery drain as doing it for one app. That's the whole reason Apple went that way instead of allowing apps to run in the background. I find on my 3GS it probably takes about 5-10% extra battery.