I would say it was a clouds filter done on 2 layers, one with the blue color and one with the dark blue. The watercolor filter and then a gradient mask. Or it might have beendone, in dare i say it, another program other than Photoshop. And the last possibilty was that it was actually painted background/image scanned or photographed.
Chad