Welcome on the board!
First things first, the accusation of betrayal to explain defeats is a bit too common in Late Rome to be entierely taken at face value : it's possible that it happened, but while Majorian's fleet was important compared to what existed before the construction he launched, it was still feeble in comparison to to what Constantinople disposed of, and probably on par with Vandalic fleet at best.
It's not like the campaign was a secret : Vandals made some opening for negociation (without promising anything) since 459, so the betrayal might have happened, especially as Vandals took with them Roman ships to reinforce their own powerful fleet, but there's nothing really saying it was essential to the defeat.
Anyhow : as Majorian took the shared lead of the WRE, things already went too far. he certainly managed to play Barbarians against other Barbarians (as Aetius did in his time, which probably inspired Majorian) by forcing them into obedience skillfully, but he never searched to crush them as he depended from their military resources : in short, it was a political-militaryexpedient.
Even Roman troops were importantly Barbarized, and with Ricimer already having too much control on imperium to really accept a too powerful and too monarchical emperor (especially if he was more and more dependent from Constantinople)...: in the mid to late Vth century, WRE couldn't really stand on its own and was either to search ressources among Barbarians or in the eastern Roman state, if not both.
Don't get me wrong, a reconquest of Carthage could likely lead late WRE to survive longer than IOTL, but with ressources already depleted, it would wear down eventually and make it unable to undergo important reforms (as Majorian's demise points), either turning it into a patrician Italy acknowledged by Constantinople as it happened IOTL (with or without Barbarian king leading it), either being swalloed up by eastern emperors that tought themselves being the only legit supreme authority even so during Majorian's reign.
We know Romans already managed to take back some points, especially places where Vandalic power wasn't that certain, such as Tripolitania, so let's assume they continue their advance. Eventually, Vandals would be forced to negociate at sword-point, as the coalition couldn't be maintained eternally, and give up several territories and assets.
Assuming Romans and their auxiliaries takes back Carthage and the "Vandalic sors", the lands in Proconcular Africa that Genseric directly took over (the rest of Africa being still under its direct authority but with fewer changes), you'd still have Vandals in the regions,
probably pushed back in their short-lived kingdom in Numidia : again, WRE depended on the presence of Barbarians in military matters.
It was sometimes suggested on the board that Majorian could "just" have resettled Vandals elsewhere but it lead to these questions, about which armies were supposed to guard Africa at this point.
Would have he settled Gothic, Suebic or Burgundian troops that made up the large part of the army?
Would have he trusted Berbers that were in agreement with Vandals?
Would have he put there the Dalmatian troops that were more or less the last of non-Barbarian troops he could rely on? Keeping in mind that most of Marcellinus' troops were made of Huns and Ostrogoths.
And how many of the limited resources of the WRE would have been used to resettle literally ten of thousands of people elsewhere in Romania while requesting the landowning elites of the resettling region to make place for them, which would be bound to backfire?
It's not that Majorian didn't have a clear perception of what was happening, at the contrary :but he had to make do. Note that Vandals generally abided by personal treaties, hence why Genseric waited 455 and Valentinian's death to advance deeper in Africa, and renewed piracy against WRE only after Majorian's death.
IOTL such a victory would "only" gave some time to WRE to die in its corner, and an extended lifespawn for Majorian. It would ask, as pointed, a slightly different strategy that wouldn't be based on the acceptance of the loss of Africa, which predominated in the mid-Vth century tough, and more subsides from ERE.
Eventually, giving the poor state of WRE at this point, it means that these regions would growingly be de facto under control of Constantinople, makin
g the ERE having a more western foothold in the west in the coming decades, a bit like Dalmatia was in the same period.
It would have interesting consequences having central Romania being swalloed up by its eastern counterpart, tough : when Africa was reconquered by Byzzies in 535, and altough the Vandalic defeat was swift, Byzantines had a really bad view of Roman Africa's history at this point, mostly ignoring the relationship between Mauri and Africans that existed at least since the IInd century, causing a costly and not that stellar (for Romans) guerilla.
They, mostly wrongly, saw these kingdoms and tribal entities as invaders (mostly helped by the threat they represented as for what mattered the coastal population) rather than parts of the old system and actively searched to crush them ; the whole campaigns of Solomon is to be understood as a tentative to gain African to Byzantium and to get rid of what was seen as a foreign presence.
ERE having a better approximation of the local geopolitics would really help preventing the mistakes made in Africa, which led to decade of semi-guerilla warfare (and decades of neglects from the late VIth onwards) after having defeated Vandals, with (for exemple) allowing policies similar to Toglita's being adopted early on (and with more success).
Basically, Romania including Eastern and Central provinces, with the Western provinces being more dominated Barbarian foedi with Roman elites more prone to keep a certain autonomy rather than readily band with Barbarians entierely (basically, having a political situation in Spain and Gaul closer to what happened in Gothic Italy).
War in the Middle-Ages by Philippe Contamine have a really interesting description of logistics and organisation of Roman army in the Vth.
The distinction between "real" Romans and Barbarians became to turn moot by the Vth century. Really roughly, what separated a Barbarian from a Roman was increasingly who they served ultimately : a petty-king or the Roman state. Militarily, Barbarians were basically equipped and fighting as Romans, with some cultural-tactics difference, but that's it.
Anyhow, foedi, laeti and mercenaries were more and more important in WRE military : you still had Roman troops (especially in Illyricum and less so in Italy, altough in all provinces), but Barbarians really dominated the game in WRE.
Now, it was rare to have them entierely separated : even in the late Vth, Roman duces and leaders integrated or led Barbarian armies.
As for their training : Barbarians weren't elite unites, but they formed trained groups that you could fairly rely on. Romans...it's more of a mixed blessing : garrison and provincial troops weren't as much untrained than unwilling to leave their regions and not specifically good at campaigning, while Roman cavalry was clearly an elite.
If it helps