I am one of the maintainers of the AWS SDK for Android. It sounds like you may be running into an issue we discovered with the latest version of the Android Development Tools and our SDK. You'll want to make sure you've exported the AWS SDK for inclusion in your app.
In Eclipse, right click on your project and select Build Path->Configure Build Path then under Order and Export make sure either the Android Private Libraries or the AWS SDK for Android is checked.
Hope this helps.
Edit
We've documented this issue on our blog.