One thing to take note of is that they specifically deny working with the NSA. They could very well be working with a contractor or another US government organization and not be lying.

Not saying that they necessarily are. Based on what I've read about the NSA I think it's very plausible that the NSA both has a backdoor from Apple, one from the baseband software (http://www.osnews.com/story/27416/The_second_operating_syste...), as well as a several hacks they've developed on their own. Their strategy is not a single path but rather as many attack vectors as possible.