Celkom tomu nerozumiem, ale problém sa rieši tak, ako som sa dočítal aj z jedného seriálu a moja skúsenosť to potvrdila, že treba mať v SDK stiahnutý posledný vydaný Android a kompilovať ním.

IMHO: Zrejme som mal stiahnutú už aktualizáciu starších verzií Androidu, ktoré žiadali prepojenie s poslednou verziou Androidu. Na druhej strane moju domnienku aj potvrdzuje fakt, že posledná verzia zaberá na disku niekoľkonásobne viac než predchádzajúce verzie. Je teda vysokopravdepodobné, že určité knižnice sú obsiahnuté práve len v poslednej verzii, aby sa šetrilo miesto pokiaľ používateľ stiahne aj ostatné verzie z nejakého dôvodu.

Označujem teda za vyriešené. Aplikácia po tomto zistení beží aj v Eclipse aj v Android Studiu. Predtým mi nebežala ani v jednom.