I'm pretty sure I know what the answer is but I'm missing at least one key thing.
So, before the final removal we must have had
MYRAPJBLJ,
so our powerful woman's name
is 9 letters long and (if everything before is simple substitutions) has repeated letters where those Js are.
In that case she must surely be
CLEOPATRA
and her lover is
Mark Antony, who spent his youth gambling in Rome.
However, if I now do the "obvious" thing and
hit CLEOPATRA with a substitution cipher whose key is derived from either ANTONY or MARK ANTONY in the traditional way -- i.e., ABC...Z maps to ANTOYBCD...Z or MARKNTOYBCD...Z --
then I find that
the thing mapping to MYRAPJBLJ has to be either THYKLARPA or RENHIMQLM; and writing out what the mapping of letters would have to be in either case gives incredibly implausible results.
Regrettably I don't have the (military?) exploits of all the Roman emperors at my fingertips, and so far my very limited research hasn't identified that second cipher key.
I'm posting this in such an incomplete state because I have to go and do something else for half an hour or so. If no one else has scooped me when I return I'll think about it some more :-).