"We were under the impression that Apple would protect us from being in a situation like this. "
Frankly it sounds like you were under the impression that Apple is able to universally and fairly adjudicate all claims in less than 24 hours. That's silly.
What if the fraudster complained about you and Apple acted too quickly and tossed your app? I mean sure your app was there first but in lots of cases the service exists before any app and you can imagine someone come in and puts out an app for foo.com before they put out the official one.
While your case is more cut and dried than most a big corporation is not going to have a different procedure for every precious snowflake. I do hope the book is eventually thrown at this creep though!