a man of his position and influence could have easily made it there

What makes you think that? Rejections at the consular elections happened all the time. They were guaranteed to happen, because the number of eligible consular candidates, the praetorians, was so enormous that only a small fraction of possible candidates reached the consulship. Highly influential individuals were rejected at the consular elections all the time. Catiline famously embarked on his conspiracy after repeated electoral failures. Metellus Numidicus very nearly failed at the consular elections three times (traditionally the number of failures before a politician stopped trying) because of his severitas.

Cato stood for the consulship in 51 and was not elected. When the civil war broke out he was only 45 and might have stood again later, but the war prevented all possibility of that.