This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
Your example Java code is exactly right; the devil is in the details, though, so perhaps some detail is wrong in your real code. Maybe it's a package thing? Make sure the package containing the interface is imported when you compile your other code (assuming everything's not in one package.)