As far as I can tell what you could do is "retire" your previous app and redirect all users to your new app. This procedure is not supported by Google (tsk... tsk...), but it could be implemented in four steps:
Change the current application to show a message to the users about the upgrade and redirect them to the new app listing. Probably a full screen message would do with some friendly text. This message could be triggered remotely ideally, but a cut-off date can be used too. (But then that will be a hard deadline for you, so be careful... ;))
Release the modified old app as an upgrade, maybe with some feature upgrades/bug fixes too, to "sweeten the deal" to the users. Still there is no guarantee that all users will upgrade, but probably the majority will do.
Prepare your new app with the updated package name and upload it to the store, then trigger the message in the old app (or just wait until it expires, if that was your choice).
Unpublish the old app in Play Store to avoid any new installs. Unpublishing an app doesn't mean the users who already installed it won't have access to it anymore, but at least the potential new users won't find it on the market.
Not ideal and can be annoying to the users, sometimes even impossible to implement due to the status/possibilities of the app. But since Google left us no choice this is the only way to migrate the users of the old apps to a "new" one (even if it is not really new). Not to mention that if you don't have access to the sources and code signing details for the old app then all you could do is hoping that he users will notice the new app...
If anybody figured out a better way by all means: please do tell.