If you are going to change the UV layout, then you'll likely want to remap the vanilla texture to the new UVs as a basis to work from. If you are using Max, you can do this with Render To Texture.
Starting with the original mesh, add an Edit UVW modifier to the stack and drag it underneath the Skin and Odyssey Trimesh modifiers, but above the Editable Mesh (if you select the Editable Mesh in the stack first, it will automatically add the Edit UVW modifier directly above it). Change the map channel to 2, and then edit the UVs as you see fit.
Now go to Rendering -> Render to Texture and (making sure your mesh is selected) under Mapping Coordinates select Use Existing Channel and change the channel to 2. Under Output click Add and choose DiffuseMap and change the save location, file type, and size as you see fit. Under the Baked Material section tick the Render to Files Only button. Hit the Render button and you should get a copy of the original texture mapped to your new UVs.
Once that is done, you can go back to the mesh, select the Edit UVW modifier and change the channel back to 1, then right click on the modifier and choose Collapse To to bake the UV changes into the mesh without destroying the skin weights.
If you have already modified your UVs, you can simply add an Edit UVW modifier and choose the Save option to save out a copy of your new UV co-ords to a file. Then you can load them back in to channel 2 on the original version of the mesh (assuming you didn't modify the mesh/change the vert number).