Create a new UV map but move the textures with the polygons? I've imported an object from an 3d data capture program in Blender, which came with an automatically generated UV Map. I'd like to create a new (more sensible) UV map based on the cleaned-up geometry, but keep the model looking the same (so the polygon-to-pixel-colour mapping is consistent).

Is this at all possible to achieve?
If the two UV maps reside on the same mesh you can use UV baking. If you create a material with the texture and the first uv layer, you can bake the diffuse color (or even the rendered result, if you make a shadeless material) and bake it to the second UV layer. Make sure to select the proper UV layers in the material texture slot, UV editor and active UV layer.