You have your debug copy still installed on your device most likely. Now you have downloaded a different copy of the same app and it s causing this error.

Uninstall the app completely from your device. Then download it from the market again and it should work.

OK I had this same issue and none of the suggested resolutions worked for me. I was signing my app the same way I have been for 2 years and the Android Market was accepting it fine, just users could not download it from the Market with the "Package Not Signed" error.

What it turned out to be was for another project I am working on I had JDK7 installed. It became the default JDK and for some reason the keytool for JDK7 is signing the package in a way that Android must not like. So I reverted to JDK 1.6.0_23 and re-ran my build and put it on the Market and everything went back to normal.

I hope this helps someone else.

On a tablet, note that if you install a debug version of the app and then uninstall it as normal (dragging to trash until it says "uninstall") that is not enough. Because tablets have the potential for multiple users, you HAVE to go to

 Settings > Apps > All

and then scroll all the way to the very bottom. There, you will see your app. Tap it, and then hit Menu in the action bar (the three dots), and then uninstall for all users. Then you ll be good to go.

There s a problem when signing APKs with JDK7. You can solve it adding this to build.xml

<presetdef name="signjar">
    <signjar sigalg="MD5withRSA" digestalg="SHA1" />
</presetdef>

Source: KIYUT Developer Blog

Recently, I signed my apks from the command line and got this error. I solved this error through the instructions in this link:

http://developer.android.com/tools/publishing/app-signing.html

$ jarsigner -verbose -sigalg SHA1withRSA -digestalg SHA1 -keystore my-release-key.keystore my_application.apk alias_name

This error usually occurs because you are trying to push an update which was signed with a different key than you used in the initial submission. You need to find the key you used the first time you published the application and use this to sign the update.

I had the same problem with my developed app.

Go to the App Manager, clear the data for the app, then force stop if it s running and uninstall it. Then try again to install from market. This worked for me.

https://market.android.com/details?id=net.trackmelite.GoogleMaps&feature=search_result

I am new to Android but I was able to resolve the issue magically :D
I used Java 1.7 with my app and used command line utilities [keytool, jarsinger and zipalign] to sign my app and got the same error.
Then I went back to Eclipse and used the Android tool "Export Signed Application Package" with the same keystore I had originally published my app with; took that APK and used the command line to zipalign it.[Had to increment the versioncode in the manifest btw]. I unpublished the old APK and published this new one. Once you do this, do not test it immediately.
Not sure how long you have to wait but mine was working 4 hours later when I checked :)