Monarchy, feodalism and religion are systems. You don't bow to the king on the top of the pole just because he's individually a swell guy - you do so because it affirms the position and concept of authority, an important thing to anyone who'd aspire to be a figure of authority themselves. Remember: organized groups over individuals. It's about the crown and what it represents, not just the guy wearing it.

If you wanted an alternative twist from this, the devils could switch sides to the former king's daughter, provided she can show her claim to be more legitimate than the usurper, and indeed this may have been part of the long con from the start. Of course, it would also mean that by helping the princess, the player characters end up helping the devils further down the line.