I had a similar problem -- it ended up I wasn't waiting long enough for the emulator to run the OS before trying to install the app. Launch the emulator and then wait for the home screen to appear before running the app in Eclipse.
or
Open Android Virtual Device Manager
select the AVD you use for your app.
Press the start button and wait for a new form to show up called (Launch Options).
Check the box "Wipe user data" and hit "Launch" button.
This should work.
--- OR ---
Open Android Virtual Device Manager
Delete the AVD you use for your app.
Create an new AVD.
Start your new AVD.
