Aha! I see what the problem is now. I do actually have a (very recent) find on a cache hidden in October 2002. The Map Hidden Month simply says "no caches found" meaning that there is no search required.
The reason I was looking is because the Month Hidden calendar grid on my profile page has not been updated yet (I'm not a paying member) and therefore I was searching for a year/month combination that looks empty, but is in fact filled. Once my stats get recalculated the profile page calendar will be updated and the cell will have a number in it.
So ... user error is the root cause of the problem ... doh!