The Heatsink should pretty much never need replacing in a systems entire lifetime unless the fan breaks and you decide to buy a new one rather than replacing the fan.
The change in the copper colour could be due to heat transfer or thermal paste. Copper cannot rust. It can become Oxidized which can make it turn a green-ish colour but that's it.
As 'charels88' said, check your temps using some monitoring software, unless its high enough to cause issues, don't worry about it
EDIT: If you could upload a photo showing what you think the problem is, it might be easier for us to work it out