There are several issues to consider, before deciding how to make the code change.
Consider the case when third parties have written code that uses or implements this interface. That would significantly increase the complexity of managing the code changes required, as well as adding a political element to the process - creating work (and cost) for other companies.
As this interface has already been implemented in many classes is a strong indicator against making changes to the current interface. The consequence on all the implementations of this new interface method need to be considered.
The fact that all these implementations have been completed without needing this new method is a warning flag that perhaps this is not really core to this interface purpose, and that this should be implemented as a new separate interface on the basis that this is a separate (but related) use of the object, and requires its own interface.
That said, assuming that we control all code that uses this interface, I would implement the new method in all classes implementing the new method explicitly.
e.g.
public class MyObject : ITheInterface
{
public void ITheInterface.NewMethod(int age)
{
throw new NotImplemented("NewMethod needs to be implemented on MyObject");
}
}
By implementing the method explicitly like this, code only calls the new implementation when it is using a reference typed as ITheInterface for the object.