I think the huge Maya bug is that you almost have no choice but to delete history to keep UVs intact. Unfortunately that also removes skin clusters. Find the script called 'fixWeights.mel' on this site. It will delete all history but (should) preserve the skin clusters. I use this a lot for just this type of problem, but it fails in some situations. Another thing that I do sometimes that may work is to duplicate the mesh, update the UVs, rebind it and use Copy Weights to get the right weighting.