In 1796, screwups in communication between both parties' electors resulted in John Adams getting a slim majority of the vote, and being elected president, with Thomas Jefferson coming in just behind him, and landing the vice presidency despite having run against Adams and not wanting the job. The rematch in 1800 featured a narrow victory on Jefferson's part, but the electors barely did better than last time, and he tied with his running mate Aaron Burr, putting the election in the House's hands, which took a week to pick Jefferson out of the Federalists' spite for him as their greatest opponent.
So the system was clearly working very badly, and the necessary change was quite clear: if the electors could vote separately for president and vice president, there would be no need to arrange for the party's vice presidential candidate to come in second. The idea that states would select wise men for the electoral college, who would in turn debate among themselves who would make the best president, was dead on arrival, and never actually happened; initially, everyone agreed that Washington would be president with Adams as his second in command, and that conversation took place long before the Electoral College met.
All that being quite apparent to the knowledgeable observer, they got to work fixing it immediately, right? Hahaha no. The twelfth amendment, stating that electors had ballots for both contests rather than every vote being for president, was proposed on December 9, 1803. The states did get to work pretty fast ratifying it, though; Rhode Island was the tenth on March 12, and New Hampshire got it to thirteen out of seventeen June 15. Massachusetts, Delaware, and Connecticut rejected it, but after New Hampshire's approval none of that mattered.
There were strong and vociferous objections to the twelfth amendment; insufficient to prevent its passage, or even significantly slow it, but three states did think it was a bad idea. Most notable was the claim that the vice presidency would simply fall to a party flunky, and not be the man that the second-greatest number of electors thought could do the job. The fact that this had never yet happened is a compelling counterargument, but just because something has not been the case the first two times it is tried does not mean that it will never be. It was pretty unlikely in this case, though, especially since if Federalist electors had gotten a few more votes, Adams would have gotten a majority and his running mate Charles Pinckney would have been one vote behind.
There was little complaint about a vice president being chosen based on popularity, but that rests largely on the popular vote being relatively insignificant at the time. Most of the states had little to no use for the people's opinion in the presidential election, and while that would change, it had not yet, and in fact had even decreased from the elections of 1789 and 1792.
Amusingly enough, though the 12th amendment was ratified only a few months before the election of 1804, it did not have any political relevance for decades. John Adams' narrow loss was not an ordinary defeat for the Federalist Party, and it went into a fairly steep decline over the next few years; Jefferson beat Charles Pinkney 162 electoral votes to 14, and while the War of 1812 was hardly an objective victory for the United States, Federalist opposition to it effectively destroyed the party as a political force.