I'm a Googler myself and my manager has told us that although 20% time is ok, we should only do it if the project has some direct contribution to the core work we work on.
Really depends on the team/department you work at, the policy is there to allow it, but different team have different culture. I believe it's more discouraged in certain departments such as Android and Social (G+) (those teams are probably under more constant pressure to "produce") than some of the more "old school" departments.
I agree it depends on the culture in each department. For someone already working long hours and under constant deadlines, I can imagine how they don't feel like they have 20% time. That's not a good way to work continuously, and hearing of certain departments or projects doing that to their teams is really saddening.
Personally, I did have very soft discouragement against wide-open 20% time. I asked around and a lot of people I talked to initially advised me against starting a 20% project so early, and especially against starting a new project rather than working on an existing one with engineers at a higher level than me. At least, they said, make sure I could get reviews out of it. That's not policy, but advice. People have their own theories about how best to get noticed and get promoted. Some of that has to do with 20% time. I guess if you're solely interested in promotion then you give more weight to such advice. I hope most Goolger's aren't solely interested in promotion.
I'm very glad I ignored that advice, both because I got to do very interesting things and because I got recognized for it, and I'm glad that I could ignore the advice because of our policy.