This happened to me when I upgraded Eclipse from Helios to Indigo (on Windows XP)
The solution was to open the Android SDK Manager and install all the updates selected by default, especially I was on
- Android SDK Tools rev 13
- Android SDK rev 7 platform tools
These updates have been updated to
- Android SDK Tools rev 14
- Android SDK Platform Tools rev 8
My project, which targets 2.2, compiles and runs in debugging now without any problems (NB, I have all the SDKs installed, including 4.0, but you can target before the SDK)
source share