I think the problem is that you are, in an attempt to give the sky drama, over-stretching the tonal range. The levels of gray in most skies is limited to just a couple of stops, so when you (we) try to expand that range into full-blown black to white it adds noise. As you have seen, it can be pretty bad in 8-bit images, and much better working 16-bit, but even that has it's limits.
You can greatly reduce the noise by working in RAW (if you're not) and creating two digital files: one standard and one toned dark for the sky. Use layer masks to overlay the darkened sky over the standard image. Using this method, you have a greater beginning tonal range.
Also, you can selectively add noise removal in only the sky area as it's primarily the darker and flatter areas that have the biggest problem.
Without seeing a full rez version as well as the RAW/original file, I can only guesstimate. However, I've witnessed those same issues from time to time (especially when trying to convert to grayscale using a heavy red filter), so I'm pretty sure that's at least part of the problem.
Chuck