He's Odysseus in Homer, but how did he become Ulixes/Ulysses when he arrived (so to speak) in Rome, where there were many people who knew him from the Iliad and the Odyssey?
And was there a separate Latin name for the Odyssey?
The most likely answer is that 'Ulixes' arrived in Rome (so to speak) before the Odyssey did. In Franz Altheim's A History of Roman Religion, he writes:
Older still [than the fifth-century BC legend of Aeneas] was the appearance of Odysseus in Italy. Even in Rome Odysseus is an early figure. All the more significant is it that he cannot have got there by means of the Homeric epic. The form of the name, Ulixes, shows that possibly the Messapians, certainly Illyrian tribes, were the intermediaries. Their homes were in the immediate neighbourhood of the home of Odysseus.
Also of note, the Liddell–Scott–Jones dictionary gives variant forms of the name that were found in the original Greek:
(also Οὐλιξεύς Hdn. Gr.1.14, Οὐλίξης prob. in Ibyc. ap. Diom.p.321 K., Ὀλυσεύς, Ὀλυσσεύς, Ὀλυτεύς, Ὀλυττεύς, Ὀλισεύς, Ὠλυσσεύς Kretschmer Griech.Vaseninschr.pp.146,147, al.; cf. Ὀλισσεῖδαι, οἱ, a φάτρα (q. v.) at Thebes and Argos, prob. in IG7.3659, Mnemos.43.372, 47.164)
In Roman transliteration those would be Ulixeus, Ulixes, Olyseus, Olysseus, Olyteus, Olytteus, Oliseus, and Ōlysseus, with a reference to some people called 'the Olissidae'—suggesting that the Latin forms are not as farfetched of variants as they might seem at face value.
As for the poem, Lewis and Short only list its Latin name as 'Odyssea', an ordinary transliteration of Ὀδυσσεία.
According to Karl Otfried Müller, Odysseus and Ulysses are versions of the same name being passed down by two different races. On the one hand, Ulysses or Ulixes (also written Οὐλίξου) was the name spoken by the descendents of the Sicels (or Sicilians), the original inhabitants of Sicily. Odysseus (Ὀδυσσεύς), on the other hand, comes to us from the Etruscans, the inhabitants of the Italian peninsula whose culture was significantly influenced by the Greeks.
Müller assserts that the difference between the names is thus due to the different ways these cultures pronounced it, especially with respect to the letters Λ and Δ:
"La raison de cette modification de nom n'est à chercher ailleurs que dans la bouche de ces races, qui confondaient aisément par une prononciation impure les lettres Λ et Δ, l'une avec l'autre, ce que nous savons notamment à l'égard des Latins. A cause de cette confusion s'explique le mot latin lacruma de δάχρυ, levir de δαήρ avec le digamma δαFήρ, oleo de la racine ΟΔ (ὄξω odor) etc. Plus tard, selon Varron, par suite d'une corruption, on fit Melica avis du mot grec Μηδιχή, et même Thelis du nom de Θέτις. C'est ainsi que Ὀδυσσεύς s'appelait aussi Ulysses et Ulixes, et non - seulement chez les Romains, puisque aussi sur un monument sicilien on lisait Οὐλίξου au lieu d'Ὀδυσσέως." ("Sur La Forme Olyseus du Nom D'Ulysse", pg. 377)
[Translation: The reason for this change in names is found nowhere other than in the mouths of these races, which easily confused them by an impure pronunciation of the letters Λ and Δ, one for the other, which we know especially with respect to the Latins. Because of this confusion, one can explain the Latin word lacruma from δάχρυ, levir from δαήρ with the digamma δαFήρ, oleo from the root ΟΔ (ὄξω odor) etc. Later, according to Varron, as a result of this corruption, we have Melica avis from the Greek Μηδιχή, and even Thelis from the name of Θέτις. Thus Ὀδυσσεύς was also called Ulysses and Ulixes, and not only among the Romans, since on a Sicilian monument one also reads Οὐλίξου instead of Ὀδυσσέως.]
Müller goes on to provide more evidence to substantiate his claim:
"L'Uluxe des Etrusques se trouve sur plus d'une pierre gravée. Le poete lyrique Ibycus, natif de Rhegium, et qui se rattache à l'école sicilienne de Stésichore, doit avoir connu ce nom du héros, au point qu'il prétendit que c'était son véritable et propre nom; car il chantait que le héros s'appelait primitivement Ulysses ou Ulixes, et que plus tard on lui donna l'épithéte d'Ὀδυσσεύς; probablement à cause de la colére divine qu'il devait subir ou à cause de sa propre colère contre les prétendants de Pénélope."
[Translation: The Uluxe of the Etruscans is found engraved upon more than one stone. The lyrical poet Ibycus, a native of Rhegium, who also was attached to the Sicilian school of Stésichore, must have known that name of the hero, to the extent that he claimed that it was his true and proper name; for he sang he was originally called Ulysses or Ulixes, and that later he was given the epithet of Ὀδυσσεύς; probably because of the divine wrath he was to suffer or because of his own anger against the suitors of Penelope.]
Müller's final comments concerning Ulysses' anger is in reference to the common etymological connection made between the name Odysseus and the Greek word ὀδύσσομαι (to be wrathful against or to hate).