In my case on Ubuntu, I did install the system image from the android sdk manager for that specific API but still had the same issue after restarting eclipse. What I did was the following:
For some reason, in the sdk/system-images/android-xx directory, sub-folders with system images (armeabi-v7a and x86) were placed within default directory. I just moved them up a level into andorid-xx directory, restart eclipse and done. I hope this helps.