The Wikipedia entry for mass nouns notes:
In linguistics, a mass noun, uncountable noun, or non-count noun is a
noun with the syntactic property that any quantity of it is treated as
an undifferentiated unit, rather than as something with discrete
subsets. Non-count nouns are distinguished from count nouns.
Given that different languages have different grammatical features,
the actual test for which nouns are mass nouns may vary between
languages. In English, mass nouns are characterized by the fact that
they cannot be directly modified by a numeral without specifying a
unit of measurement, and that they cannot combine with an indefinite
article (a or an). Thus, the mass noun "water" is quantified as "20
litres of water" while the count noun "chair" is quantified as "20
chairs". However, both mass and count nouns can be quantified in
relative terms without unit specification (e.g., "so much water," "so
many chairs").
Some mass nouns can be used in English in the plural to mean "more
than one instance (or example) of a certain sort of entity"—for
example, "Many cleaning agents today are technically not soaps, but
detergents." In such cases they no longer play the role of mass nouns,
but (syntactically) they are treated as count nouns.
It also observes:
Some nouns have both a mass sense and a count sense (for example,
paper).
Cheese appears to be another of these nouns with both a mass sense and a count sense. The Oxford Dictionaries website includes the following as a definition of cheese:
[COUNT NOUN] A complete cake of cheese with its rind.
It offers the following example sentence:
"the cheeses are trimmed and wrapped in sterilized muslin."
This is sufficient to reassure me that I could legitimately say, "Nine of the cheeses are finished and we have three more to go." The word cheese can, then function as both a mass noun and a count noun, meaning slightly different things in the two uses.
It also seems clear that most mass nouns can make an appearance as a count noun. The Wikipedia article cited above notes:
Some mass nouns can be used in English in the plural to mean "more
than one instance (or example) of a certain sort of entity"—for
example, "Many cleaning agents today are technically not soaps, but
detergents." In such cases they no longer play the role of mass nouns,
but (syntactically) they are treated as count nouns.
I've tried but haven't been able to find an example of a noun that cannot become a count noun in this way.
The lab tested 7 gasolines. 12 different coffees are on offer.
I admit that I would like the sentence above better if it said "7 brands of gasoline" or "7 samples of gasoline", but nothing about it seems to me wrong or even particularly surprising. Even abstract nouns seem to be amenable to this transformation:
FDR's Four Freedoms
10 Hopes I Have For Past Loves (Title of Huffington Post Article)
The question seems to deal less with the 'less/fewer' issue than the 'at least/at fewest' one.
'At least' is a restrictive particulariser. These refer to a specific number, a subset of a larger quantity, and as the lowest limit of that larger quantity, seen as a magnitude.
'At fewest' is illogical, as 'fewest' is a superlative, which implies 3 or more things being compared. It refers more to the objects being compared more as multitudes or specific quantities, rather than a magnitude of a large, unknown quantity.
I would therefore argue that 'at least' is correct in this case; 'at fewest' is not.
Best Answer
I think you are correct in that if a noun is unambiguously mass or count then the qualifier doesn't matter, the meaning can be taken from the noun.
However compare: I ate too much fish vs. I ate too many fish.
If the noun is ambiguous in that way, then the meaning must be taken from the qualifier. So if you mistook "fish" for a term that was always mass or common, then you could produce an ambiguous statement.
(Inspired by Shinto's example)