This looks like the effect of noise reduction at high ISOs. Heavy NR is common in compact cameras with small sensors. Fujifilm cameras of that generation did it very well compared to others of the time, but there's only so much blood you can get from a stone.
On most modern high-megapixel point and shoot cameras, you'll see this even at low-ISOs if you pixel peep. It's important to note that in most cases, this is actually okay, because for printing or at common display sizes it'll look just fine. Better quality gives you more room to crop, of course. And in this case the sky looks particularly bad, so with this camera I'd try to stick to lower ISOs.
More advanced models often have the option to turn off noise reduction, and I usually do, because I prefer the look of noise to this "painted" blur. Or, if you shoot RAW, you have many, many options for more flexible noise reduction in post.