Interesting discussion! I'd have jumped in sooner, but Comcast seems to be blocking e-mails from this server. Here are my thoughts (and please forgive me if I leave some worthy nation out or bring up one that is in the game by mistake).
North America: I also endorse the suggestions of Québec, the California Republic and Deseret. Texas is already in. There's at least one other "ahistorical" entity that wasn't: the Provisional Government of Oregon, which ran most of the Pacific Northwest from 1853 to 1858. In Our Time-Line, it was more of a vassal of the U.S. than a full-fledged nation, but in that period, at least some residents wanted either independence or to join Canada instead. What if the U.S and Britain, instead of dividing the Pacific Northwest peacefully, had fought over it as Polk threatened to? What if the U.S. had had a worse reputation or worse relations in the 1850's?
There were a lot of historical Native nations in the West which either fought, or might have, or at least which the U.S. might have been forced to release. Since many by then had been forcibly relocated, they might have cores on their traditional homelands, and perhaps even unification missions, such as a successful Navajo rebellion retaking the Southwest to become the nation of Dinétah. Or, a player might choose not to be as aggressively expansionist as the U.S. was; what might happen then?
You asked, however, for ahistorical nations. Well, then: what if Sequoyah had become independent, probably during the Civil War? What if it had incorporated the rest of Oklahoma? Or, what kind of nation would a successful slave revolt in the South have established? Many thought at the time that one was likely. They were probably wrong, but there were successful slave revolts in Haiti and elsewhere, and some people went to great lengths to either prevent or start one in the South, so there's an argument for making it possible. The reason to handle this as something different from an ordinary revolution is: before 1861, the Federal government would have been hostile to such a rebellion, but once the Civil War began, or upon Emancipation at the very latest, the former slaves would likely join the Union. It's also interesting to speculate about what revolutionaries in the Mexican Cession might have done, since in the game such a revolt could happen. Rejoin Mexico? Declare a new California Republic? What if Mexico no longer exists, or the California Republic still does?
South and Central America: I second the nominations of Gran Colombia, New Granada and a Republic of Central America (which could represent any of several attempted unions during this period), although all of these existed. The game might also include the Peru-Bolivian Confederation, or just represent it as an annexation of Bolivia by Peru.
Europe: Flanders, Wallonia, Corsica, Galicia, Catalonia and the Basque country come to mind as potential nation-states in Western Europe that didn't happen to exist during this period. A particularly severe series of defeats for France or Britain might allow a partition at bayonet-point of, say, Burgundy or Scotland as puppet states. There are many Central and Eastern European nations that formed later, but might have been carved out of Austria, Russia or the Ottoman Empire earlier, for example Slovakia.
Asia: I second the idea of a potential earlier appearance of Israel. (Theodor Herzl's novel Altneuland, while not very realistic, set its Zionist utopia in 1923 and had a great deal of influence in the early 20th century.) At the least, the Balfour Declaration was the kind of momentous decision that ought to be in the game, and it's easy to see how a different timeline might have seen something like it happen earlier, later or not at all. There was an important Pan-Arabist movement at the time; this might be represented by creating Syria with cores on its neighbors, or even the option to release a Greater Syria. Muhammad Ali's Egypt might be another path toward an Arab unification, although that also probably does not require a new tag. An independent Palestine (perhaps along the lines of the 1919 Faisal–Weizmann Agreement, or else created by a rebellion under the right conditions) makes sense as a potential nation-state.
If the Mughal unification of India continues to represent the historical origins of that empire, there should be another tag for a native unification of India or Hindustan.
China spent much of this period in civil war, and the Uighurs, Manchurians and Tibetans all saw at least brief independence.
Kurdistan and Turkestan also seem like plausible, ahistorical nation-states.
Africa: I second the suggestion of a possible Afrikaner nation. Maybe a unified Bantu nation, under the right leadership, might possibly have been large and cohesive enough to make a real go of it, especially if it had faced separate colonization attempts from minor European powers rather than a carve-up by the great powers.
The Pacific: What if the U.S. had made Spain release its remaining colonies after the Spanish-American War, rather than taking them over, or had lost to the Filipino insurgency? What if it hadn't annexed Hawaii? Could there have been a Polynesian, or even Austronesian, unification? What if the Dutch East Indies had become Indonesia sooner, or had broken up, e.g. creating an independent Java? What if New Guinea had become an independent Papua?
Some of those ideas are more plausible than others, of course. Discuss?