I've just finished making some updates for a company's Android app, only to realize that they no longer have the private key that was used to sign the original release that went to the Android Market. If I understand correctly, this means that these changes can't be released as an update to the original app. I think the best option is to pull the original app from the market (it doesn't have many downloads or reviews) and re-release the app signed with a new key. However, I'm worried that Android Market might not allow an app to be released which is practically identical to an app that has already been released (e.g. same name, same icon, mostly the same functionality, etc.).
Has anyone been in this situation before? Did google allow you to re-release as a separate app to the Android Market?