Were there any traditional native american/new world cheeses? In what parts of the New World were different cheeses found? Or were they tragically cheeseless?

There is one important prerequisite for cheese: domesticated dairy animals. So /u/Hinmatoowyalahtqit is asking the right question here. Our only good candidate for dairy production in the Americas is the llama. In the modern Andes, llama milk is consumed, but not at a level worth mentioning. Camelids have rather small mammary organs and have not been bred as dairy animals.

There's no archaeological evidence for the practice that I know of, but we do see two historical documents mentioning llama milk.

Bishop Vincente de Valverde wrote in a 1553 letter that folks in Cuzco were selling:

lana de ovejas de aca; queso y leche; algodon, pescado seco, quando se toma; cantidad en las pesquerias; coca... Llama wool; cheese and milk; cotton, weighed dry; stuff from the fish markets; coca leaves...

His is an isolated mention, and if you read Spanish you can see that the colonists had to make up a few phrases for new encounters. Here Valverde calls llamas ovejas de aca, "the sheep from here." Najera in the next reference calls them ovejas de tierra, "Ground Sheep." There's some questions over whether Valverde did mean what we know as queso and leche today.

Alonso González de Nájera mentions that los indios consumed llama milk in his ~1605 book. However, he points out that they do it especialmente en tiempo de hambre, "especially in times of hunger," and that they can get no less milk from a llama than they can blood from a ram's head without doing it harm (read: not much).

And that's about it. Valverde does not specify that it is leche de llama, and Najera writes too far after conquest to assume it happened before. We cannot say that it never happened, but it's not worth bringing up in any discussion of pre-Columbian diet.