Эта проблема была вызвана моими старыми проектами на новой машине, на которой не был установлен более старый Android SDK.
Чтобы исправить, просто зайдите в project.properties и посмотрите номер вашей старой версии:
# Project target.
target=Google Inc.:Google APIs:3
Просто обновите номер версии, например, так:
# Project target.
target=Google Inc.:Google APIs:7
Вы обнаружите, что Eclipse подбирает нужную версию SDK и начинает работать.