הוֹשֵׁעַ means "saves", while יְהוֹשֻׁעַ means "God saves". Rashi explains:
And Moses called Hoshea…: He prayed on his behalf, “May God save you from the counsel of the spies.” [The name יְהוֹשֻׁעַ is a compounded form of יָהּ יוֹשִׁיעֲךָ, May God save you.]- [Sotah 34b]
Sotah 34b (in the Babylonian talmud) relates the following (Soncino translation):
And they went up by the South and he came unto Hebron (Num 13:22) — it should have read ‘and they came’! — Raba said: It teaches that Caleb held aloof from the plan of the spies and went and prostrated himself upon the graves of the patriarchs, saying to them, ‘My fathers, pray on my behalf that I may be delivered from the plan of the spies’. (As for Joshua, Moses had already prayed on his behalf; as it is said: And Moses called Hoshea the son of Nun Joshua, [meaning], May God save thee [yoshi'aka] from the plan of the spies.) That is the intention of what is written: But My servant Caleb, because he had another spirit with him.
According to the rabbis of the talmud, Moshe knew to expect trouble and prayed on behalf of his assistant, going so far as to change his name. (Apparently a midrash says he knew this through prophecy; that site does not cite a source, but Jewish Virtual Library is usually credible.)
Yehoshua retains his new name, יְהוֹשֻׁעַ, in the book named after him.