The Android SDK is provided by default as 32 bit version only. If you’re on Linux x64 (Intel/AMD), you have to install the 32 bit compatibility layer, otherwise nothing will work proper.
In my case it was easy on Ubuntu (at the time of this writing i’ve been running 12.04):
apt-get install ia32-libs apt-get install sun-java6-jdk
Without the ia32-libs, adb will not run!