I had the following similar error on Ubuntu 13.10:
Cannot run program "/usr/local/android-sdk-linux/build-tools/19.0.3/aapt": error=2, No such file or directory
And this answer fixed it for me:
To get aapt working (this fixed my issues with the avd as well) just install these two packages:
sudo apt-get install lib32stdc++6 lib32z1