Is it true that colored coins or digital assets (counterparty / ethereum / nxt assets / etc.) have an issue of paying fees? I'm looking to setup my own digital asset or coin on either counterparty or nxt assets or ethereum to distribute to my loyal customers, but 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. 

Is this a flaw in these systems or is there an alternative solution to this problem? Or what solutions have others come up with thus far?
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).