I assume that the tria nomina will remain in use theoretically, but expand into a more flexible and genealogically oriented system. In real ligfe, people will likely have several names depending on the linguistic community they interact with, and a Latin name part of which is used in polite society.
It is likely that the sounds of the name will be changed, but the spelling is liable to be quite conservative. You could e.g. have a
Marcus Antonius Beffae f. Adilulfi f. Gaimari f. Adilomeri f. Adilulfus Flavus Cursor
Which is Marcus Antonius (for citizenship dating from the third century) Adilulfus (this is the name he uses in polite company) son of Beffa, son of Adilulfus, son of Gaimarus, son of Adilomerus (the genealogical element) Flavus (his 'signum' - the blond - and service moniker) Cursor (a nickname - the runner or messenger).
To any official, he is M. Antonius Adilulfus
To a Roman acquaintance of rank, he is Adilulfus
To a friend or fellow soldier, he is Flavus
To a fellow Germanic or Celtic nobleman, he is Athalulf son of Beffa son of Athalulf son of Gaimar son of Athalmer
To his childhood friends, he is Cursor (or Lopere)
To the Gallo-Roman peasants he pushes around, he os probably known as 'domine' to his face and something like 'beergut' behind his back.
In Church, they will call him Marcus (unless he gets a separate baptismal name, though that didn't really catch on OTL)
Something like this, with older families having entirely separate naming systems amnd people from the lower classes just having a first and gentile name baptismal name (if different), byname and possibly another name in a different language.