Comment 10 for bug 983100

The Ubuntu package 'gnome-icon-theme' does not provide any weather-related icons.

Ubuntu packages which do provide appropriate icons (there may be others, these are the only ones I have installed currently) are:
'gnome-icon-theme-full' 'humanity-icon-theme' 'ubuntu-mono'

The "High Contrast" and "unity-icon-theme" themes also provide appropriate icons, but I do not know what packages they are from.

So, what should the dependencies be? Or should things be "Recommended" instead?

FWIW, the third-party themes "Faenza" and "Faience" also provide appriopriate weather icons (I am using Faience, so until stumbling across this page I was unaware of this dependency issue)