After spending a few hours: I restarted the Android SDK Manager
and at this time I noticed that I got Android SDK Platform-tools
(upgrade) and Android SDK Build-tools
(new).
After installing those, I was finally able to fully compile my project.
Note: The latest ADT (Version 22) should be installed.