The holidays got hectic for me, but I still wanted to leave an answer for you. Sorry for the delay.

I would take a page out of patio11's book. People give gifts for a LOT of different reasons. The trick for getting use out of this site is to be available at the exact right moment someone needs it (difficult, but doable) OR be memorable enough to be found when the person is thinking about gift giving (much harder, but also doable). Let's focus on the first objective: being available at just the right moment.

Thinking about how people shop for gifts on the internet, Google is an obvious first step (and the easiest to approach). patio11 makes a Bingo Card Creator which is pretty generic on its own. But the next thing he did was quite ingenious. He started generating custom landing pages for SPECIFIC segments within his product's market. For example, he would make a Christmas Bingo Card landing page, or an Astronomy Bingo Card landing page. He has a system which practically does this for him, requiring very little work up-front and a great deal of value over the lifetime of his product. I think it would be quite easy to replicate this process to work for you... making landing pages for Birthdays, Bar/Bot-mitzvahs, Graduations, etc. By creating custom landing pages, you can take advantage of Google's traffic to point people at microsites you've created for each (very specific) segment of the gift giving market (which is HUGE, btw). If you ask ANYONE (expecially Ramit Sethi) about marketing, they'll tell you to "niche it down".

There's a really good "How-to" direct from patio11 himself at http://mixergy.com/patrick-mckenzie-interview/. You can also find more detailed information about his process at http://appsumo.com/hacking-content-creation/. (If you're feeling generous, earn me a few dollars of credit by using this link instead: http://appsumo.com/hacking-content-creation/?r=cbhz). I should also mention that patio11 shares LOADS of information about how he monetizes his Bingo Card creator on his blog. I'd start at http://www.kalzumeus.com/greatest-hits/

Another way people shop for gifts on the internet is asking their friends about the person. This might take a little more effort on your part, but consider extending what you've started and let people create "Gift Profiles" for each other on your service. People already have wish lists on Amazon so why not make that experience a little more exciting (and memorable). While I can't tell you the best way to go about this, but there are plenty of interesting ways you could consider. For example, make a game out of it. How well do you know your friend? or "This or That Gift" where they narrow down a gift choice gradually getting points for gifts closer (instead of further) to what the recipient might like. Or, let people personalize their own gift list for specific occasions. Or allow people to put an embedded (and personalized) gift widget on their site. If the experience is good enough, people remember your service as well as be in the right place at the right time. Use these ideas to provide a better gift recommendation EXPERIENCE (this is key) than your competition.

Clearly, none of these things would have helped you in time for Christmas anyway, but Christmas is only one of many opportunities. Hope this helps.