Android 4.0 AVD を作成しました。AVD を起動してアプリを実行すると、4.0 AVD の横に赤い「X」が表示されます。その AVD を選択すると、アプリがインストールされません。
私のAndroidManifest.xmlには<uses-sdk android:minSdkVersion="8" android:targetSdkVersion="16"/>
、4.0デバイスには問題ないと思います(SKD 16は4.1です)
Android Device Chooser のスクリーン ショットを次に示します。