Bitcoins aren't exactly mainstream yet. Giving the average person a paper wallet would net the same reaction as giving them Monopoly money.
Sure, keep telling yourself that.
I gave my sisters paper wallets, and their reactions ranged from very interested ("I'll have to read up on what this Bitcoin thing is") to amused (she: "I'm going to sell them later tonight". me: "sure, go ahead, but I'll laugh so hard if price is 10 times higher next christmas". she: "okay, I'll wait a bit before I sell them")
I would say it's a bit too deep into the tech pool to give as a present to the very young or elderly, but for anyone even remotely interested in tech-y stuff, it's a nice idea.