How to deal with IP rights infringement?

Recently I received an email from AppStoreNotices@apple.com, saying that company called AppDetex on behalf of Facebook claims, that my app infringed its trademark.

Apple wants me to resolve this matter directly with complainant and send them "written assurance that your application does not infringe Complainant's rights"

I see that the problem is with the name of my app. So, I'm ready to change it, however, I received a direct email from complainant that they want me to remove my app and publish a new one:

While we appreciate that you wish to, or may have modified your app, we don’t review or consent for the republication of apps.
Please carefully review and comply with the policies and guidelines published by Instagram and Apple and publish a new app. 


Did anyone happen to have similar cases? Is it possible to resolve this without removing the app?

And second question, what is an appropriate form of assuring Apple that I have an agreement with complainant?
It sounds like 'complainant' is going after you hard. You may need an IP attorney to guide you.

You wrote "I see that the problem is with the name of my app". If that were true,  change the name, tell Apple that you are not in violation of any trademarks and ask to be re-approved. Better would be to have that IP attorney write you a letter that you could send to Apple.
How to deal with IP rights infringement?
 
 
Q