From my experience these are some things that you could try.
First thing to try is simply cleaning and rebuilding the project. project -> clean
Have you enabled installation of apps from unknown sources?
Have you renamed the apk file manually at all?
The other reason you may be experiencing this is due to conflicting android versions. What version are you packaging the app for and does this match the version that your phone is running? You may have to export a signed version.
Also try adjusting the android:minSdkVersion to match the version your running. You may be building packages for a newer version than what you are running.