Just saw this thread and hope my answer will still be useful to you.
Lake Powell is best for paddling in fall. Summer = nuthouse full of powerboats and jetskis; also extreme heat. Winter = iffy camping conditions.
Spring's air temperatures are often warm to hot, but the water is extremely cold in early spring (deep water). If you go, avoid spring break periods.
I like fall because the water is still warm from summer and the crowds have lessened. Note that I did not say they go away! The concesssions run discount programs on houseboat rentals in fall, and these things will be your competition for campsites.
Both spring and fall you can pretty much count on strong winds on at least some days, so figure in some layover days if you're doing a kayak-camping trip. If you're setting up a basecamp in the developed campground, you can go hiking instead of paddling on the craziest wind days.
It's beautiful there. If you kayak-camp, make sure to sleep under the stars at least one night! No bugs, and usually clear skies. Although you won't hear the sound of tides coming and going, little pockets in the sandstone cupping gently moving ripples can "sing" to you all night.