Right, so from what I remember from my Russian courses is to think of it like this: нет, не было, and не будет are basically the present, past, and future forms of the same phrase, all requiring that you use the genitive case. нет чая = there is no tea, не было = there was no tea, не будет чая = there will be no tea.
In this case, the sentence is trying to convey that "there was no tea". Try to think of "не было" together as a single phrase and as the past tense form of "нет". So, if the sentence read "В магазине нет чая", we would translate this as "There is no tea in the store." Replacing "нет" with "не было" just changes the tense from present to past. And the fact that "чай" is inanimate does not play into this situation. The same thing would happen with an animate noun such as "женщины" (women): "В магазине не было женщин" (There are no women in the store).
While that would convey a similar message, a Russian translation for "Tea was not in the store" would be "Чай не был в магазине." The sentence from the lesson, "В магазине не было чая", conveys the idea that "there was no tea" as opposed to "the tea was not". Your sentence could perhaps imply that a specific kind of tea was not there, while the sentence from the lesson implies there is no tea at all.