I believe you are correct. In fact, when Muhammed fled to medina, there were 3 major clans of Jews in the city. To gain their support, he origionally had the muslims pray towards Jerusalem, however, he eventually betrayed them, and changed the rite to praying towards Mecca. I don't think you have to go to far to change him from starting the final religion to making the final revision to Judiaism. Maybe he is saved as a child by a Jew. The problem is going to be convincing the Jews that he is the messiah. Also, the diaspora has been ongoing for a time now. So getting the message out will be hard. Not sure whether having to convince isolated communities instead of the beurachracy of a kingdom will make things easier or harder. It also opens the question of what he does once he has secured the Arabian penninsula. Conquer Jerusalem?
EDIT: I did some checking, and discovered some interesting tidbits. Apparently, Muslims prayed towards jerusalem form the beginning, because Muhammed saw himself as a phophet of the same vein of the old Hebrew prophets. And according to muslim sources (the only ones avalible), the Jewish tribes were betraying Muhammed, and conspiring with his enemies. Not quite sure which version to believe.