For an application, once you upload it to the Google Play Store, it is uniquely identified by the package name you gave it. I've found an article that details what can't change once an app is uploaded.
From that post:
Once you publish your application under its manifest package name, this is the unique identity of the application forever more. Switching to a different name results in an entirely new application, one that can’t be installed as an update to the existing application.
So that explains why people can't simply update the application. It's because to the Android operating system it is an entirely different application. Even if all the code is the same, that small change differentiates it.
If you read slightly further:
Just as important as the manifest package name is the certificate that application is signed with. The signing certificate represents the author of the application. If you change the certificate an application is signed with, it is now a different application because it comes from a different author. This different application can’t be uploaded to Market as an update to the original application, nor can it be installed onto a device as an update.
And finally:
If the signing certificate changes, trying to install the new application on to the device will fail until the old version is uninstalled.
So, in summary, you changed things you shouldn't have. Keep your package name the same and sign with the same key every time you upload an app to the store.