I got fed up using Blender to make sky boxes (due to the UI), so I wrote an application that makes skybox textures:
http://gethome.no/clund/div/SkyBoxer.zip
You can use and distribute the thing for free. Don't take credit for it, and don't charge for it (as if…). Note that I am not a professional programmer, so it might not even work on other systems than my own. It runs on my Mac Pro with 10.5.6. Supposedly, it also runs on 10.4. I think it's a universal build.
I haven't done anything in the way of memory management or garbage collection, so the thing is an absolute pig. When rendering high resolution skyboxes on a mac low on ram, it'll hog your entire system and Finder might tell you it (the app) has crashed. It hasn't (probably). Just give it time.
To use the thing, open the source image (should be an equirectangular projection — also called an equidistant cylindric projection), select the resolution from the popup menu, render, and save.
If you want some surreal skybox textures, here's a small bundle I made from NASA images:
http://gethome.no/clund/div/Planetpack.zip
The source images are included, so you can see what an "equirectangular projection" looks like (also look it up on wikipedia). You can make images that work like this by using the polar to rectangular coordinate (and vice versa) transformations of Photoshop.