You should try fresh cheese curds, they are best when they are so fresh they squeak when you bite them. They are also good deep fried.
I'm a native speaker (American) - and I also used "a" in this case, because simply saying "new and tasty cheese" didn't sound right w/o context, "A new and tasty cheese" implies w/o context there are other kinds of cheeses, while "new and tasty cheese" could but sounds odd (though grammatically correct also).
In English it can be counted though. You have a cheese plate with different varieties: "And here is a new and tasty cheese for you to try."
Cheese is both an uncountable/countable noun depending on the situation. In this case the article "a" is really attached to plate and cheese works like an adjective to describe what kind of plate it is. You can say "I buy a lot of cheese" or "these cheeses are delicious" but "I have a cheese" doesn't sound correct. In the OP's comment, the "a" does make work there. Hope that makes sense!
I don't think the plate has anything to do with it. "What do you have for me today, sir?" "A new and tasty cheese." If anything, it's the unspoken "variety of" or "type of" that is receiving the article. Nonetheless, this is quite common and should be accepted since there are many situations in which it is employed.
Not disputing the fact that cheese is more frequently uncountable. It's the fish vs. fishes scenario... "how much cheese do you have?" vs. "how many cheeses do you have?" Either can be correct depending on what you want to know.
Definitely agree on the part that it "a new and tasty cheese" should be accepted! Cheese is a word that it really depends on what you're talking about and what kind of message you're trying to get across.