Sort out a complex UV map for a complex mesh
Select all the UVs in UV/Image Editor, from the UVs menu select UVs From Islands. 



Then in Object Data tab create a new UV Map and unwrap the model. While all the UVs are selected, create an image in the new UV Map where the new texture will be baked and keep this UVMap selected.



Then make sure you have a material and the original texture is applied there using original UVMap.

 

Click on Render tab and in bake menu select textures and click Bake button.



In the same way as described, it is possible to bake multiple materials that are using same or different UV Maps, to a new single or multiple UV Maps, each with separate texture.

The described above steps are aplicable for Blender Render internal engine. Workflow for Cycles is a bit more tricky though is well depicted here:
Possible to bake texture to new UV map?