Ted Cruz says that his father fought against Batista.

[Xithras]

52. Indeed. The Revolutionary Directorate (or the 13 March Movement) was an anticommunist army.

Once Cuba began to destabilize, a number of factions joined into the fight hoping to direct the outcome after Batista fell. The Revolutionary Directorate was a large army of young college students who left school and formed their own anti-communist, anti-Batista army. They engaged in open combat against the Cuban government for months and seized regions of the country before eventually choosing to fight alongside the communists.

After the communists seized power, these groups engaged in a six year war against the communist government in order to overthrow it. This fight is now known as the Escambray Rebellion, or The War Against The Bandits in Cuba. The army was receiving supplies from the United States, but that support was pulled after the Bay of Pigs invasion failed...the rebels didn't last long after that. After their collapse, the Cuban government spent years hunting down and executing former RDS fighters.

Now, I have no idea if Cruz's father was in the RDS, but they are just one example of the forces fighting against Batista who were NOT pro-Castro. It's entirely possible that his story about his father is true (and his fathers age would have been consistent with the RDS fighters).