Trouble is, I didn't use Terragen to render the clouds, but took sky pictures from CGtextures. It would seem the grain is within those photos themselves. I've tried to replace the clouds today in PS and noticed the grain wasn't really gone, even when using a new set of cloud pictures.
But, since you mentioned Terragen, I might go that route. It might even work out better, since you have a good perspective feel in Terragen, giving a better feel of depth.