Well, since there is no step-by-step info on how Ironclad made their backdrop textures (you will notice they have used a spherical map with cut-off poles to preven texture pinching) I can't really tell you how to make a texture that would fit existing backdrop meshes - I tried various techniques, but could not get rid of seams as none of them were precise enough.
My advice is to create a new skybox mesh and UV-map it yourself. That way you will have the information you need to make precise placement of textures and avoid seams.
The other trick you may want to try if you don't want to make new meshes is to use your new images but adjust the alpha on the edges/seams so that in fact only portions of the skybox texture show, while seams are made transparent. Both ways work fine.
And yeah, Photoshop is the best for texture work.
