We know that Odysseus is a strong leader, a great warrior, and very clever, which are all very admirable traits, especially in Greek culture. However, he’s also arrogant, destructive, intolerant, and did I mention arrogant?
These traits make it difficult for him to be a hero to Muslim Arabs at the time when Sinbad’s story started circulating. These traits are simply incompatible with the values of the culture. Couple this with the fact that Odysseus is Greek (aka a foreigner) and it’s clear that he’s got to go and make way for Sinbad.
Sinbad’s traits more accurately reflect his culture, giving them someone they can aspire to be like. Moreover, Sinbad is reachable. All of the Greek heroes are kings or demigods (sometimes both) whereas Sinbad is a merchant. He’s not even a warrior. He’s out pursuing an honest trade, and while he ends up in extraordinary circumstances, his adherence to the values and traits of his culture are what allow him to overcome, and he is rewarded with great wealth (which he proceeds to spend and then lose before the next adventure).
Heroic myths all possess a certain amount of nationalism, elevating one figure as the ideal representation of the culture. The Greek heroes, in fact, did not represent Greece as a whole. The modern nation of Greece didn’t exist in antiquity. Instead there were the separate city-states of Athens, Ithaca, Argos, Thebes, and Corinth, just to name a few. Each of these different states had their own heroes, most of which were represented in the Trojan War when they grouped together to whoop on Troy.
Sinbad is one representative of the Arab nations in their rise to the Golden Age of Islam. Not only must he have the values of these nations, he must be from them, as well.