I use the Weather Icon plugin. Are you sure you followed this instruction?
"Then edit the weather.php file to point to the
'wicons' folder and set the other options listed there.
make sure you set write access on the cache folder."
My icons are in a folder with 755 permissions also, so you should be fine there. I used the full http path to the icons folder in the weather.php file.