I did a phone interview with Google last week. I was given the exact same counter problem as mentioned in the article. I can verify that I was not asked to sign any NDA at any point.
- We would be interested in having you at/as ... but before the specifics, you signed an NDA, right?
- No, I have not.
- Oh, then good luck, bye.
For what it's worth, I had an overall positive experience interviewing with Google.