The key is in understanding the statement, "Cannot reduce the visibility of inherited method".
Let's say you have a class Person having a public method getAge(). You have another class say MortalityRiskCalculator, that has a method calculateRisk(Person p) :-
This above code calculates risk for any given Person and is only dependent on the person's age. However, in your business model, you could have several types of Person such as Manager, Worker, and Owner. All of these may extend from Person class thereby inheriting the getAge() method.
Now, what will happen if you override getAge() method in Manager class and make it private? It will break all the code that depends on Person class's getAge() method. When you wrote Person class, you promised that getAge() is accessible to all and based on that promise, someone wrote the MRCalculator class, which has no idea about what all kinds of Persons you have. If you make the getAge() method private in Manager class, you are breaking that promise because Manager IS-A Person.
Same thing happens with an Interface. As Richard mentioned, methods in an interface are public. Any class that implements an interface promises that all the inteface methods that it implements will be public. If you make any such method "less accessible than public", you are breaking that promise.
This fulfilment of contractual obligation is critical in developing component based applications.
You will see the same concept in action when figuring out which exceptions an overriding method (or a method that implements a method declared in an interface) is allowed to throw. Try it as an exercise
As an hint, just think of what will happen to the existing users of the interface/superclass if you introduce a new exception in the throws clause of the implementing/overriding method.
HTH,
Paul.