Это один из недостатков Android Market, хотя я могу понять, почему они так поступили. Он просто не был предназначен для бесплатных и платных версий вашего приложения (они утверждают, что для этого нужна круглосуточная политика возврата, но вместо этого она используется для пиратства):
В любом случае, самое простое - написать скрипт сборки Ant (или любой другой язык сценариев, который вы используете). Выполните поиск по замене имени вашего пакета по всем файлам .xml и .java. Затем сделайте сборку своего приложения там. Рефакторинг вашего кода - это боль, чем стоит ИМХО ...