Actually, the title is a bit misleading. We already had money exchange in game but you could only exchange for higher denominations, and you had to pay extra.
But now...
All you have to do is go to Worrem Dhoshi in East Hydlaa and give him 10, 50 or 250 Tria. It doesn't matter what denomination or combination you use. He'll ask you how you want it, and you can pick your denomination of choice. (Yes, you can give him a Circle and get a Circle back if you're bored.)
His only limitations are that he won't give you a combination of denominations back (so you can't get your 250 as 4 Octas and 5 Hexas in one step. If you need it like that you can get it in octas, then exchange 1 Octa for 5 Hexas) and he can't handle more than that. While I'm sure it would be lovely if he can exchange 100,000 tria into 400 Circles all at once, I'm sorry, he can't.
We're not responsible for lost coinage if you're exchanging a coin and it crashes. I suppose in that case you should be thankful you'll never lose more than 250 tria if it happens.
As you may have noticed this service is now FREE, provided by the treasury. Enjoy!