Problem of colored-coins/assets and other coins with a parent/child relationship of paying for fees with only the parent currency I've looked into building out my own coin, but it was best to just piggy back on top of an existing blockchain like how colored coins and counterparty is doing it. But when going on this route, I run into the problem of having to pay the fees of using the blockchain in the native currency. 

Say if I was to create a game token based off of the bitcoin blockchain on top of counterparty, I still have to pay the fees in Bitcoin. Which my users will not have even if I distributed my game tokens to them. Now they will be stuck with the game token without being able to send it anywhere. 

One solution was to monitor these addresses, and just fund them a small amount of btc just for them to pay for the fees. Is there a service out there that does this? 

This issue is also apparent in other coins like ethereum and nxt. They give the ability to create your own child coins within their blockchain but you are stuck with the coin unless the holder has the native currency.

How are others solving this problem?
It's definitely a common problem found in a lot of those platforms that make it easy to create your own colored coin/token. Asking users to acquire the native token, such as Bitcoin with Counterparty and NXT with the Nxt blockchain, is usually not a good way to start off your relationship with that customer. Some people may be fine with it, but it greatly hinders mainstream use. 

Ardor solves this problem with child chains that allow child chain creators to have the users on their child chain pay transaction fees in the child chain token. A bundler (could be the child chain creator) would collect these fees and pay the Ardor main chain for transaction processing. So, ARDR tokens would still be needed, but your users wouldn't need to touch it at all. 

You would still need to re-distribute your acquired child chain tokens though, but the Asset Exchange that will be on Ardor will be a great way for you to sell them back to your users. If a USD child chain exists (kinda like Tether and USDT), then they could purchase those child chain tokens directly with those USD tokens, much like getting game tokens at the old arcade.