Когда в коде следует использовать интерфейсы (Java)?

DevMan прав - по парадигме всегда!
На практике - любой написанный код (класс или интерфейс) требует расходов времени на создание и сопровождение. Сопровождать примитивный класс проще, чем примитивный класс и его интерфейс.

Поэтому на практике, обычно, пишут интерфейсы:
1. Как необходимую часть паттернов;
2. Если "интерфейс - это контракт взаимодействия": разрабатывается библиотека или компонент, здесь интерфейсы - это часть неизменяемого контракта;
3. Хорошая практика - все сервисы делать с интерфейсами. К этому подталкивают многие фреймерки JAVA, как пример: Spring и OSGi (Apache Felix);
4. Для JUnit тестировая. Пример: при тестировании бизнес логики, реальные сервисы заменяются тестовыми заглушками. Соотвественно класссы бизнес логики должны использовать интерфейсы, которые при реальной работе земеняются реальными имплементациями, а в тестовом окружении - тестовыми заглушками.

1, Абстракция нужна везде, где будет проходить ось изменений системы. А интерфейс - основное средство достижения абстракции в Java. Из этого следует п.2.
2. Всегда, когда нужна абстракция (за исключением случаев, когда абстракция должна обладать состоянием. В таком случае вместо интерфейса придется использовать абстрактный класс т.к. интерфейс не может обладать состоянием).