Refactoring often requires breaking interfaces. The same forces that created the code you wish to refactor also created the interfaces, therefore the interfaces are often less than desirable, which means if you are continually improving code you must also improve the interfaces.
You can't possibly say your code base is improving and not improve the interfaces as well. There's nothing special about interfaces that means they were correct. There's nothing special about interfaces that means they can be a fixed center around which everything turns.
If stuff breaks then it breaks. Your UnitTests and compiler will help you fix it. It's no different than any other changes.
Yes, refactoring often requires changing interfaces. So, Don't publish interfaces prematurely. Modify your code ownership policies to smooth refactoring -- RefactoringImprovingTheDesignOfExistingCode, chapter 2, Problems with Refactoring. It also talks a little bit about what to do when an interface is published.
When you're using other peoples' published interfaces.
Better wrap those external interfaces so you can keep control. See ShieldPattern, AdapterPattern, BridgePattern, ProxyPattern... The basic idea is to create an interface that you control, and the rest of your code uses. Behind that interface, you make calls to the code that is not under your control. This allows the rest of your code to be mostly immune to changes in the external code - just change your wrapper code. Also, you can often insert workarounds for bugs in the external code.
When other people are using your published interfaces
Say you've written some kind of widget which has an interface so that programs can embed the widget in their user interface, tell it to do things, and get information back from it about what it's doing. If you decide to ReFactor the interface between your widget and the outside world, third-party developers using your widget are going to curse your name because now their code doesn't work, and they have to finish the ReFactoring that you started. This happens regularly with LinuxKernel, GeeLibCee? and GnomeDesktopEnvironment.
That's why interfaces with dependencies from code you can't change shouldn't change. They should aggregate with new versions, be replaced by new versions and eventually deprecate when (and if) old dependencies migrate to the new versions.
Every piece of code as interface to some other piece of code. Logically then nothing can be refactored.
If you can't change the code that depends on an interface and all of the code falls into that category, then yes, nothing can be refactored. Refactoring requires the ability to modify code.
Distinguish between internal and external projects.
Even on a large internal project i can break interfaces and recover because we have control. If you have interfaces to paying customers then you would be much more committed not to breaking those interfaces.