[Legolas]

I'll go ahead and post the answer I typed up earlier.

'Gandalf,' the old man repeated, as if recalling from old memory a long disused word. 'Yes, that was the name. I was Gandalf.'

You see, this was not Gandalf's real name.

He is actually an immortal being called a Maia. An angellic-like spirit that was sent to Middle-earth in the form of an old man (just like the other four of the wizards) by the Valar (14 very powerful similar spirits that ruled Arda from Valinor, the place they sail to in the end) to aid the people of Middle-earth in their fight against Sauron. He existed long before Middle-earth was created, and will exist long after its end.

The balrog was a similar being - formerly a Maia. This is why Gandalf tells the Fellowship, "Fly! This is a foe beyond any of you. I must hold the narrow way. Fly!" As Peter Jackson pointed out in the movie, swords were of no use there. He and the balrog battled for a long time, and after destroying the balrog, Gandalf's physical incarnation on Middle-earth passed away. His spirit went back to Valinor where the Valar sent him back to fulfill his mission.

You see, the wizards, when sent to Middle-earth, were not allowed to display their full power or use it. The Valar only wanted them to guide the people of Middle-earth - not fight the battle for them.

When they sent Gandalf back, he was allowed to display more of the power he held inside. He was the only one of the five wizards to keep to his mission. It was kind of strange for Gandalf to be sent back and forth, as he appeared differently in Middle-earth. Not that we'll ever be able to understand it exactly, but I imagine that when he was in Valinor or Middle-earth, his time spent in the other probably would've seemed like some alternate reality or another life he had lived until he got used to the land and his form of being again. You would be disoriented too for a little while if you switched back in between two very different lands in which you were presented in such different manners of appearance and ability.

His 'true' name (that is, his original name in Valinor) was Olórin.

He probably seemed more Elvish because of his behavior in Valinor. He was indeed a Maia, but a great elf-friend in Valinor. The Silmarillion says this about Olórin's nature:

for though he loved the Elves, he walked among them unseen, or in form as one of them, and they did not know whence came the fair visions or the promptings of wisdom that he put into their hearts. In later days [his time as Gandalf, that is] he was the friend of all the Children of Ilúvatar, and took pity on their sorrows; and those who listened to him awoke from despair and put away the imaginations of darkness.

(text in brackets is mine)

For more information, read The Silmarillion and 'The Istari' chapter of Unfinished Tales.

Treebeard's talk of Gandalf returning was more of an instinct. He did not actually know what I told you about Gandalf. Tolkien even says so...Treebeard is wise in some areas, but he is not Tolkien:

(from Letter No. 153)

Treebeard is a character in my story, not me; and though he has a great memory and some earthy wisdom, he is not one of the Wise, and there is quite a lot he does not know or understand. He does not know what 'wizards' are, or whence they came (though I do, even if exercising my subcreator's right I have thought it best in this Tale to leave the question a 'mystery', not without pointers to the solution).