I'm a huge fan of card games that can be played with a regular deck of cards, and I play Cuttle with my kids somewhat regularly. It's a fast-paced game, but you do have to get over the initial learning curve of the effects. I find just printing out a piece of paper with a quick reference on it helps.
As others have alluded to in the thread, teaching people the rules is a barrier. As I looked around for a professionally printed game, I found a game that was very much like Magic the Gathering, but also just a single box of cards called Mindbug.
Turns out it was designed by some folks that brought Richard Garfield in near the end of its design and he ended up having some say in the final product. I've played it a couple of times and each game is only played with a random subset of the cards, so the combinatorics create a lot of replay value.