You say they're a "relatively new player", so OK maybe it wasn't their very first game.
Yeah, you're quite right, but admittedly it wasn't their 50th game, either.
They've played maybe a half-dozen times so far. Again, like with the original poster, he's an experienced gamer, and we had already played several introductory games with base cards plus a splash of color.
I didn't even realize how many mechanics there were until I set it up. I just avoided painful cards like cursers, discard and trashing attacks, too-many-decision cards like Count, and overpowered cards.
Part of the problem is that I really enjoy showing the game to Magic players, because it scratches a lot of the same itches, but without the money treadmill. The huge variety and number of mechanics is part of the hook!
That said, even for Magic players, it's a learning curve.
I definitely try to read my audience, though. I wouldn't play that kingdom with most inexperienced players. The player in question definitely enjoyed the game and will keep playing, and he appreciated the strategy advice and notes about card interactions.
There's no substitute for playing a lot of games in order to get better at it. I'm still trying to figure out the best way to help new players after I've hooked them.