Do any venerable DMs or players have any suggestions about how to get past this conflict? Am I "doing it wrong?"
I am far from venerable, but here's my 2cp
What you did wrong was to have this scenario in your game. Do not try to put a case like arresting an innocent PC (if I understand right, he's being setup and did not commit any crime) in the game
unless you're confident that the players will be fine with it.
IMXP there'a lot of people who hate when their PCs become victims of injustice because this unfortunately is one of the most heart-breaking, hope-draining and enraging thing that can happen in real life.
Let the evil guys in the story have the exclusive on being unjust, because many players will not just submit to the accusations if they think their PCs are innocent, and some may even attack the guards.
How did you honestly expect the story to continue, had the player played "correctly"? Did you expect him to surrender to the guards, face the accusations, probably go to jail and wait to be saved by his pals? Were you going to put some trial into the story? This may actually be interesting for some gaming groups, but personally I wouldn't like that at all, I would find it boring (I rarely enjoy trials in movies and TV-series). Also for me D&D is actually a game where I want to see the BBEG get caught, killed, and possibly worse, and if the good guys are caught into something like that, I want it to be the evil guys' work (which obviously should then be caught, killed, and possibly worse), not the regular, legitimate law.
I understand that perhaps I am a simpleton. I admit that the game for me is an evasion. I see innocent people being punished in real life for crimes they didn't commit, and I hate it. At least let me have some confort from our fantasy stories.
Oh and one more thing...
unless your players are actually your friends and you're sure they're fine with it, avoid any reference to sexual harassment and violence against children in your games. I went even as far as consciously deciding to stop mentioning children and offspring in my campaigns (except of course in harmless situations) to prevent any chance of having to deal with sensitive issues: no baby orcs in my game = no trite paladin dilemmas about what to do with them.
So how would I handle your case now? I would talk the player into not running away and tell him that the guards will believe him and not proceed to arrest, and if the player doesn't want it, I'll scrap the whole incident and pretend it never happened.