Eventually reached an answer thanks to j_random_hacker's comments.
The answer basically uses the cycle properties of an MST - if an edge is the most expensive edge in a cycle in G, it cannot belong to any MST of G.
The provision for changing the costs of k edges to arbitrary values implies that we must show that e' is the most expensive edge in at least k+1 cycles which are all edge-disjoint except for e' itself. This way, even if the arbitrary change of k edges causes e' to not be the most expensive in k cycles, it will still be the most expensive in the last cycle.
Given a graph G, edge e' and parameters k and epsilon (both > 0):
Temporarily delete all edges in G more expensive than e' (this ensures that e' is the most expensive in whichever cycles we find)
Now, set one end of e' to be a source (s) and the other end to be a sink (t). Set capacities of all edges to be 1. Flow integrality ensures that since all capacities are integers, we will get an integral flow.
See if you get a flow of value at least k+1. If yes, flow decomposition will give you as many edge-disjoint paths from s to t as the value of flow. Convert all these paths to cycles by adding e' to them - this way you have k+1 (or more) cycles in which e' is the most expensive edge and which are all edge-disjoint except for e'. You can now safely say that property (*) holds for e'.
I have a way to deal with epsilon if it is an integer. In step 1, delete all edges that are more expensive than cost(e) + 2*epsilon.