Modifying all classes which implemented by interface

Lets say I have an interface like

interface IMessage
{
    void DoSomething();
    void DoAnother();
}

Lets say in a big project 100 classes implemented this interface. But if I add a new method to IMessage interface like Foo();

interface IMessage
{
   void DoSomething();
   void DoAnother();
   void Foo();
}

So my other 100 classes which implement this interface has to change.

So does something wrong here? Changing all clasess? I hear about Open Close prensible so I used interface but in that situation, what is the logic?