Was the weight glued on the inside of the rim or clipped onto the rim lip? Those latter ones usually leave more stubborn stains.
I would try rubbing it with some Bug&Tar Remover (TurleWax) - it's a white milky fluid - applied to a cloth.
Another thing to try would be to spray it generously with Kaboom (available at Walmart or other supermarkets), wait 15-30 minutes, and then rub off with a cloth. But I think B&T Remover would be more potent here.
Afterwards, be sure to wax the rims.
Is the rim clearcoated or not? If not you can use something like Mothers Mag and Aluminum Polish on the rims.
If they are clearcoated then a mild polish used for paint should work. If its a glue deposit then a tar remover (like Pete suggested) or some kind of mineral spirit should do the trick.
Usually the corrosion is from the weight scrapping off the clearcoat. The only solution I know is to buff the rim and repaint the clearcoat. You can request that they only put the weights on the inside, but that will not give you as good of a balance.