Hopefully the letting agency can sway the LL that he'd get a better price for it decorated as it is than if it was bland and magnolia.
What I would point out is that you moved into an unpainted house, you asked for permission to paint, at your own cost and now are being asked to change it to a colour it never was before, again, at your own cost.
So. It is not possible to return it to how it was - unpainted.
You are unwilling to repaint it at your own cost given that you bore the cost of the original painting job that the LL should have paid for.
It's being advertised at a dearer rental price and they have explained it's because of the decor and improvements you've made - so they can't argue that and claim that your colour choices devalue their rental to allow them to keep your deposit. It's one or the other.
I've lived in rentals up until now and in each case, common sense has usually prevailed - if the agency can explain that the LL is likely to get more for the house as it is, you are probably in the clear - it all boils down to money.
Actually, my last rental was the only one where it wasn't bloody magnolia. Now, the colour choices of the LLs wife weren't to my taste at all but it was so nice to live somewhere that felt like a home and not a beige soulless rental.