IGL s.v. ἄξενος II (p. 84, R) cites a (pentameter) line from Ov(id):
Euxeinus qui nunc Axenus ille fuit.
This supports the point that the Axine was 'afterwards called the Euxine'
The closest passage to this in Ovid is Tristia IV.4.55-56:
frigida me cohibent Euxini litora Ponti:
dictus ab antiquis Axenus ille fuit.
The source of the first half of the pentameter remains unknown.
The juxtaposition of the Latin forms of the <ει> and <ε> variants is noteworthy.