Part of the problem by this idea is that the territorial claims of the various states over the Appalachian mountains were not governable. Virginia claimed the entire Old Northwest, New York Claimed a large portion, as did Massachusettes, etc. However, the regions in those states desired independence from the main state due to that distance and separate identity. As we see from the State of Franklin, those revolts were already starting and, as the western provinces continued to grow, power would shift away from the eastern elites and be forced across the mountains. In the times before railroad, telegraph, etc, these regions could not be effectively governed from such remote capitals. You see this again in New Mexico, where the territory was split due to the south and west not being easily governed from Santa Fe.
The Dakotas are the easiest one, but they were split after the proposed annexation of Santo Domingo failed; either way, the GOP wanted 4 new Senators. That makes 49. Of course, Absaroka might end up popping up anyway...
West Virginia is another obvious one. Make that 48.
I suppose the point about Georgia is salient enough; they aren't blocked off by the mountains, and it seems reasonable that they could have maintained their territory to the west. Combine with a more successful West Florida, which removes the ports for the Yazoo. Make it 47.
If Deseret actually shows some functions of sovereignty in the leadup to the Mexican-American war, and applies for annexation to the US all the same, they might be admitted straight-away as a state, with them acquiring an area roughly analogous to the Utah territory at original size, so Nevada is part of it. 46.
New Mexico and Arizona will eventually split; they are too large and, while Arizona is missing the Gadsden, they still possess what will become the Las Vegas region. Even absent gambling, that triangle will become a larger population center. Considering the size of the territory and the remoteness from Santa Fe, it will eventually be split in two for easier management.
However, New Mexico mirght retain a salient to the northeast as it did at first. Perhaps, in compensation for losing Arizona, they gain a bit more of the old Texas claims in what is Colorado. This is enough to make what would become Colorado too small (what with Utah taking half of it already) and as such Colorado isn't formed and it is divided between nearby regions. 45.
That makes it as low as I can imagine without drastic intervention. Tennessee hated being ruled from North Carolina, and wanted to leave. North Carolina hated being ruled by South Carolina, and as such left. Maine hated being ruled from Massachusetts, and as such desired to leave. I repeat myself, but removing the slavery controversy doesn't remove that key part of the issue that is involved.
It is also not so simple as giving up the land and claims either. That land was sold to the federal government, which paid by taking on the various states' war debts. You could butterfly that, of course, but you'll alter the dynamics of the rest of the country's growth, and that may actually hamstring part of it (as hamstrung any Articles of Confederacy US would be).
Your easiest case would be a modern PoD, but that would effectively end the United States as they currently are, as that would abridge the sovereignty of the states as they are today.