One thing you may want to try is alpha channels. I tried it on your image (hope you don't mind [img]/ubbthreads/images/graemlins/tongue.gif[/img])...
I selected all, copied and pasted into a new alpha channel. Once you have your channel, you'll need to adjust it (in this case I just bumped up the contrast) to make the bridge (and anything else you don't want having blue over it) black and the sky white. Made a selection from the channel, and then used a gradient (blue to transparent) for the sky. Whole thing took maybe five minutes. (Of course, to fine-tune everything will probably take longer [img]/ubbthreads/images/graemlins/tongue.gif[/img])
Hope this helps!