I agree with Teasel. If the replacement is a new experience (new route, container some distance away, different hunt, or whatever) then make it a completely new cache. If it's essentially the same cache as before with just a slightly different hiding place then use the same cache page.
Sorry to hear you lost the cache. I recently archived my only micro when it was stolen for the second time in two months.
Do not go gentle into that good night.
Rage, rage against the dying of the light. (Dylan Thomas)