I have to agree, without specifics no one can give real advice. To use a car analogy, I can tell a mechanic "it's making a noise like NEP NEP NEP" but until they plug in the code reader and actually get their hand dirty they can't give an estimate for the work. We have to know both the terms, the ACTUAL WORDS. Even then, perhaps filing a claim himself in the Google ecosystem might shake it up a bit, at least for the first claim. The second sounds more serious. Anyway, I have these questions:
We need a time frame, how long has it been since he contacted the second person? There's a big difference if it's been a few business days, a week, half a month, etc. How many times has he attempted contact with them?
What are Google's stipulations to NOT have apps pulled. "Work it out", does that mean the complainant must withdraw their complaint? Does Google even vet these before sending them out?
What are the actual words? Names of the apps?
Names of the people complaining against you. There may be people who have been attacked in the past by these two who might be able to "help", look in forums for people with similar charges brought against them (especially on the second guy.)
But you need to trademark these terms as your own, in your market, ASAP. Since you know what their trademarks are, register your own with those words but make it even more specific so it only covers you. Get a copywrite on them too. If this is too $$$, well, then probably give up since this is "the cost of doing business".
Your state might have people who can help with this, even Oklahoma has a small business agency with "free" lawyers who do trademark and copywrite. At this point, your apps have taken a life of their own. You'll probably need to form some type of LLC, register all this in it's name...and I don't know how trademarks, their dates, etc work in the law since IANAL. If you get one too, even if it is after the initial complaints, if you file your own complaint...might have to play hardball.