I have previously posted a solution that, among other features, lets you relink a lookup column. This article introduces a new tool that does lookup column relinking only.
Get the code here, and ensure you use the correct version.
The difference between the 2007 and the 2010 version is that in 2007, you must place the code in a web part in the site where the lookup column resides.
You can target another site, but must run the code in the site where the column you want to alter is located.
In the 2010 version, you can change the source web as long as you target a web within the site collection.
If you like the solution, buy me a beer using the Beer button on the top right of this page.