Android Studioでプッシュ通知の実装時に、
デバッグ実行すると以下のエラーが起きるようになった。

Installation failed with message INSTALL_FAILED_DUPLICATE_PERMISSION perm=net.xxxxxxxxxx.yyyyy.permission.C2D_MESSAGE pkg=net.xxxxxxxxxx.zzzzz.
It is possible that this issue is resolved by uninstalling an existing version of the apk if it is present, and then re-installing.WARNING: Uninstalling will remove the application data!Do you want to uninstall the existing application?

アンインストール使用としても、失敗する
DEVICE SHELL COMMAND: pm uninstall net.xxxxxxxxxx.yyyyy
DELETE_FAILED_INTERNAL_ERROR

原因
パッケージ名が別のアプリでC2D_MESSAGEが登録済みでした。
2つともアンインストール後に再度インストールすることで解決。