Having some passport not recognized by some country is not that unusual. It's pretty much certain to happen somewhere for passports of countries with partial recognition.
Someone else mentioned passports of Northern Cyprus (which is only recognized by Turkey), which according to Wikipedia, is only accepted in 6 countries. But there are many other countries in the same boat.
The Republic of China passport: The Republic of China is recognized by 21 UN members plus the Holy See. But its passport is accepted in almost all countries. However, there are some peculiarities. According to Wikipedia, a few countries (Argentina, Kenya, Laos, Nepal, Serbia) will issue the visa on a separate sheet, not on the passport itself, presumably due to not recognizing the passport. Brazil apparently will require the person apply for a Brazilian laissez-passer as the document to put the visa on. China (People's Republic of) will issue some kind of permit instead.
The page for Kosovar passport does not explicitly mention any country where it is not accepted. But common sense would dictate that it is not recognized by Serbia.
The Nagorno-Karabakh passport is not recognized anywhere, according to Wikipedia (though it's unclear if that means it cannot be used anywhere). For Transnistrian passport it says "not valid for travel to most countries" (not really sure what that means). The pages for Abkhazian passport and South Ossetian passport do not explicitly mention any country where they are not accepted. But again, they would be at least not recognized by the countries that their territory is claimed by (Azerbaijan for Nagorno-Karabakh, Moldova for Transnistria, Georgia for Abkhazia and South Ossetia). The page for Palestinian Authority passport also does not mention where it is not recognized; but for that case it is conceivable that it could be recognized everywhere. For Somaliland passport, it says it is accepted in 8 countries as unofficial travel documents, which probably means it is not accepted mostly everywhere else.
South Koreans visiting North Korea will be issued a visa on a separate piece of paper.