I use Photoshop mostly for the kinds of adjustments that I usually made in the darkroom through dodging, burning, chemical manipulation, choice of paper, etc. For my personal use I have no problem retouching out an object that intrudes into the frame that I missed while photographing, though I rarely do it. I know my job is not to miss it, but I'm content to catch it on the second go-round if the image is otherwise important to me.
For your own pictures -- for your wall or for sale -- you get to make the rulebook, but competitions have their own. I would probably not drop in a cloud, but as others have pointed out, it was done in the darkroom too, and has a long history. Jerry Uelsmann's creative manipulations are certainly legitimate, unless they were to try to pass themselves off as straight, documentary images -- which would be a tough sell, admittedly.
I enjoy doing fairly straight photography, using photoshop as a pretty traditional darkroom equivalent. But as long as a photo does not misrepresent itself, I'm fine with even extreme photoshop practices. It's been some time since photography could be excepted naively as a direct representation of the world before the lens.
