I use Eclipse and run the ADT stuff within it. I tried to create a new Android virtual machine and kept getting the error mentioned in the title. I verified all permissions in all applicable directories, and still had no luck.
It turned out the problem was that I was running the ADT on 64-bit Linux (Mint 17, to be specific), and I needed to install a couple of 32-bit libraries. Here is the list:
libstdc++6:i386 libgcc1:i386 zlib1g:i386 libncurses5:i386
Thanks to Pavel Kazlou for providing the list here: