The choice of words tends to be a good tipoff.
When someone answers a different question than the one asked, or uses different terms that are more flexable in scope or definition. Originally they focused on 'no direct access' and ' no back door'. As a computer person you can understand that there are lots of ways to get information in or out of a system that can be characterized differently than the above phrases. It's like talking to child about a how they got the cookie they have in their hands, did they take it, did they pick it up, did they steal it, did the find it, did it fall off a truck, did a guy name Vinny give it to them because hes a nice guy, etc. And what is the legal definition of 'cahoots' anyway?
A lawyer is talking, so you have to be extremely careful with what they say. "I’m not sure I can say this more clearly: we’re not in cahoots with the NSA and there’s is no government program that Google participates in that allows the kind of access that the media originally reported."
Okay, so it's not a program, maybe it's a project, or a NSL, or and executive order, or a collaboration. Having shown themselves to be complicit in a lie of omission (not saying anything because of gag orders) And having changed their statements a few times their word is suspect and needs to be examined.
It is imposible to prove a negative. That kinda sucks for Google because they have brought into question our trust in them and it may take a good long while to rebuild that trust, even if they tried to.