I thought that the data would be encrypted with your device's key, not Apple's key.

Here's a quote of his from the Charlie Rose interview: We’re not reading your email, we’re not reading your iMessages. If the government laid a subpoena on us to get your iMessages, we can’t provide it. It’s encrypted and we don’t have the key.

Perhaps that's not the case? Or rather, perhaps that's literally only the case with iMessage? I don't think iMessages are ever stored on iCloud, and instead only ever propagate from device to device...