Ah, but were all those troops combat troops? Don't forget Engineering districts, Coast Artillery, supply posts and bloated command staffs which were all part of any army of the period. In light of that 7 combat brigades is not too far out of the question for a 36k total army strength. Most of the US strength from its founding was militia/national guard units that could be called up and used in a timely manner for the wars of the 19th Century.
Don't forget the strategic situation either. The US had a big Navy from the late 19th century on and peaceful neighbors through much of 19th century period in V2. Sure the Mexicans had several civil wars, but they rarely spilled over to the US until the 20th century. Until WWII the US didn't see the need for a large active army as long as the navy was large enough.
..... Some people might have considered my post a cheap joke at the expense of the usual 'history didn't play out exactly as it did in real life after 100 years of divergent events' crowd... but very well, I concede completely on this point with no attempt at argumnt whatsoever.