Had this sort of problem today after upgrading to latest ADT/SDK. Took me quite a while. Checked that i used google-apis (for maps), uses-library, cleaned the project etc.
Deleting the .project and adding a fresh one (create new android project) finally solved it.