No problem, especially considering that they don't actually know that he died, merely assumed so.
In alphabetical order:
Aragorn (88) of the long-lived race of Numenor has known Gandalf (the old man) for 63 years at the time of his fall and rebirth. He knows that he isn't an elf or of Numenorean race, so his questioning of Gandalf's background has long ago been satisfied or put aside. In the context of the story he has many other things of greater import to occupy his mind.
Boromir (41) is dead at the point of Gandalf's return.
Denethor (89) has known Gandalf his whole life and has little respect for him. He also isn't really aware of Gandalf's death and rebirth, especially given Gandalf's efforts to conceal his "upgrade" from casual observers.
Elrond (6515) knows Gandalf's background. He doesn't see Gandalf again until after the fall of Sauron.
Fangorn (Treebeard; age unknown, but ancient) has likely known Gandalf for the last 2000 years, and encourages the hobbits not to be hasty. It seems unlikely that he has truly accepted Gandalf as dead before Gandalf reappears.
Frodo (51) has known Gandalf for at least 30 years. He doesn't meet reborn and upgraded Gandalf until after the fall of Sauron and expresses surprise.
Galadriel (7185) knows Gandalf's background (from back in Valinor) and appears to hold some doubt as to whether Gandalf is truly lost.
Gimli (140) has known Gandalf presumably for more than half his life at this time (since the fall of Smaug) so is in the same situation as Aragorn.
Legolas (approx. 2000) has had the opportunity to know Gandalf for around 2000 years. I doubt there's any surprises in this for him.
Merry (37) has known Gandalf for most (maybe all) of his life. He is surprised by Gandalf's return, and he and Pippin discuss how he is different. This in the context of having just seen Saruman deposed by Gandalf.
Pippin (29) is the same circumstances as Merry.
Sam (39) has known Gandalf for about as long as Frodo, but from a greater social distance. He also doesn't meet Gandalf 2.0 until after the fall of Sauron. If Gandalf were to sprout wings and fly I don't think Sam would question it much, writing it off as the business of his betters.
Saruman (Curunir; predates the world) is fully aware of Gandalf's (Olorin's) background, but is probably unaware of Gandalf's death and rebirth. He certainly isn't aware of the upgrade until it is too late.
Théoden (71) has known Gandalf his whole life, isn't in the clearest of minds when Gandalf turns up, and is unaware of Gandalf's death and rebirth. After his recovery everything has a new shine to it, so I doubt he much notices the change in Gandalf until the confrontation with Saruman. It's possible at this point that Théoden sees Saruman as lesser (which he is) without recognizing Gandalf's elevation.
Wormtongue (45) through his association with Saruman is more familiar with Wizards than most, but still is unaware of Gandalf's death and rebirth. He sees Gandalf's return as an impediment to his job, but doesn't see the upgrade to Gandalf until it is too late.
I don't think anyone else in the narrative is really familiar enough with Gandalf for their reaction to be relevant.
So we see that the mortals associated with Gandalf that known of his death and rebirth prior to the fall of Sauron are Aragorn, Gimli, Merry, and Pippin; Not a particularly large group.
As such, those most likely to question his background in the light of his death, rebirth and upgrades are Merry and Pippin, who have been familiar with this "old man" doing somewhat miraculous things (with fireworks) their entire lives.
His apparent comfort in walking into the courts of king and steward and speaking on equal terms would cause them to wonder at his background.
We see Pippin asking questions that get evasive answers. How long do you continue asking these types of questions knowing (and fearing) what he is capable of, and sensing his unwillingness to answer?
Prior to his death and rebirth he is, as has been said, a legend to mortals, and known to the immortals.