I wonder why the Romans changed his name from the Greek Oddysseus to Latin Ulysses.

I've wondered the same thing. There seems to be more going on here than simple language differences. Herakles > Hercules I can see, particularly as it sheds light on the nuclear > nucular issue. Perhaps one of our resident linguists can weigh in.