To me it's a matter of viewer/customer expectation: if you present this as photojournalism then it's not OK. If you present it as advertising for a vacation package, then it might be OK if the clouds are "native." I.e., if the scene is typical of the area, but you just missed the ideal photo conditions, then it's OK. If it's "art," i.e., exists purely for the aesthetic value of the image then it's a matter of personal taste. Some, like thepancakeman, seem to believe that photography is just like painting, but using different brushes, paint and canvas. Others, like me, think that what makes photography unique is that has an element of "reality" that painting does not have. To me, a photo is less interesting if it is "less real." Cut and paste is easy, but being there to capture the real thing is hard. I generally expect every photo to be essentially real, unless it is obviously not. "Obvious" here means either declared by the photographer, or obviously manipulated to the point that no reasonable person would mistake it for real. For example, I assume that a photo of Sasquatch driving a flying saucer is not real.
If you are fooling your viewer then it's cheating, with minor exceptions where fooling was an important message of the photo