However, there's something about the way this guy asked the question that makes me unsure whether I would have correctly answered it on the spot. It's somehow detached from both application, and the logic that underlies it.
If the question had been asked as: "Is there any relationship between Not A and Not B" I would have instantly gotten the correct answer.
...But the way he asked it, it comes across as a question about whether Not A implies Not B which of course does not follow the given. I realize none of those words are in actually in there, yet the phrasing of the question somehow leads my brain into filling in the gaps in that way. My suspicion is that this is actually a common thought pattern and perhaps those being interviewed may have fallen into a similar trap.