cletus, eta_carinae, and everyone else already gave great points, but I want to add one more to the pile: Google really cares about culture fit.

From the way I understand it, there are two main goals for hiring:

1. Always raising the bar by finding people who are better than the average Googler.

2. Find people who would fit in well and Googlers would want to work with.

This adds another dimension to the way you could perform in your interview. Keep in mind that not only the answer counts, but also how you answer, what kinds of questions you ask, what your attitude and personality is, etc. I have no idea if this was a factor in your outcome, but it's just another thing to consider.

Lastly: Don't be afraid to reapply after a year or so (I've interviewed at Google three times before joining)—prior results aren't held against you.

Disclaimer: I'm also a Google employee.