Is it true that colored coins or digital assets (counterparty / ethereum / nxt assets / etc.) have an issue of paying fees?
I noticed that even if I created an account for my customers, they have no way of sending that token back to me when they wish to redeem it as these platforms require their transaction fees be paid in their native currency.


That's kind of true for Counterparty. The transaction fees are paid only in Bitcoin (which is a native currency of Counterparty), but not in Counterparty (XCP) which is the other native currency.
If holders want to redeem their token(s) for a good or service, they only need to pay a small transaction fee (that goes to bitcoin miners) which is expected.

I wouldn't say other systems that do require their own currency for this are flawed, it's how they decided to do things, as karask noted. Counterparty's approach emphasizes the use of BTC while XCP have been only where necessary (at least that's been the case so far).