It would have been more surprising if he hadn't been able to identify a Balrog. Elves grow up steeped in lore, and surely Legolas would have heard about how his ancestors fought Balrogs in ages past. And the Balrog he actually identifies, known as "Durin's Bane", played a key role in Legolas' people deciding to live in the region of Mirkwood in which he was born and raised; it also bore partial responsibility for the relative lack of communication between the Elves of Mirkwood and Lorien in Legolas' time.
From the blog titled "Ask Middle-earth":
The elves of Mirkwood and Lorien used to have a much closer relationship. They were both originally Nandorin/Silvan communities that, during the Second Age, came to be ruled by Sindarin leaders that shared the same ideology (see this post for more information.) And we see this older relationship exhibited in what Legolas tells the fellowship about Lorien when they first arrive - almost all the stories he tells are about Lorien as it was in the Second Age, or even the early Third Age (specifically, talking about Amroth and Nimrodel) instead of more recent information (specifically, Galadriel and Celeborn.)
The relationship changed, however, when the balrog, Durin’s Bane, appeared in Moria (in the year 1980 of the Third Age.) The emergence of this ancient and evil creature (that had a special cultural relevance to elves, since many of the Noldorin and Sindarin elves had fought balrogs in the First Age) created a panic in Lorien. Many of the elves took this as a sign that it was time to sail west to Valinor, and it was also at this time that Amroth (Lorien’s king) and Nimrodel left Lorien entirely. With their leader gone, the elves that remained in Lorien were a bit lost, but it was then that Galadriel and Celeborn arrived and took leadership of the community. The appearance of the balrog affected the elves of Mirkwood too, however. In the Third Age, the reduced population of the elves of Mirkwood (many of them had died in the Battle of the Last Alliance at the end of the Second Age), had been steadily moving towards the northern parts of Mirkwood. But the balrog appeared just as Sauron was settling in southern Mirkwood, and the combined threats drove the rest of the elves far to the north - and far away from Lorien.
In light of the crucial part Durin's Bane played in shaping Legolas' early years, it is no surprise that he was able to identify it on sight. It had driven many of his kin out of Lorien, and forced his family and friends to flee to the northern borders of Mirkwood, leaving their homes and causing relations between Mirkwood and Lorien to break down. It is clear, when we read Legolas' dialogue in Lothlórien, that he knows little about the Elves of Lorien, despite the fact that his people used to go there frequently:
‘It is long since any of my own folk journeyed hither back to the land whence we wandered in ages long ago,’ said Legolas, ‘but we hear that Lórien is not yet deserted, for there is a secret power here that holds evil from the land. Nevertheless its folk are seldom seen, and maybe they dwell now deep in the woods and far from the northern border.’
-The Lord of the Rings, The Fellowship of the Ring, Book II, Chapter 6: "Lothlórien"
Furthermore, Durin's Bane also had a role in the mutually hostile relationship between Elves and Dwarves, because the Elves blamed the Dwarves of Moria for releasing the Balrog from the deeps in which it had dwelt for many years. As far as many Elves were concerned, the greed of the Dwarves had forced many of the Eldar to leave Middle-earth before they otherwise would have done. This point has been raised on this very site, as well as on the aforementioned blog:
As discussed in a post about the Doors of Moria, by the end of the Second Age the elves and the dwarves actually got a long pretty well. That changed the year 1980 of the Third Age, though, when the balrog was woken up in Moria. The elves, who had a strong and very negative cultural memory of the balrogs of the First Age, were very upset by this event. Many of the elves living in Lorien fled the region entirely, and the increased orc population following the balrog’s awakening affected the elvish settlements in Lorien, Mirkwood, and Rivendell.
The real problem is the blame-game being played out at the same time. The elves blame the dwarves for awakening the balrog. Gandalf says it best in LOTR, saying that the dwarves “delved too greedily and too deep.” The elves say that the dwarves brought this on themselves - and the rest of Middle Earth - because they were greedy and didn’t know when to stop mining.
The dwarves, on the other hand, point out that it wasn’t the dwarves who created the demand for mithril (which was what they had to dig so deep to find.) Rather, it was the elves who had the strongest love for mithril, and payed the highest price for it. They don’t go so far as to blame the elves entirely, but are highly offended by the elves’ implication that the dwarves somehow deserved the balrog and the misfortune that followed it.
Celeborn is so angry when he hears that Balin's expedition had reawakened the Balrog of Moria that he wants to kick the Fellowship out of Lorien, especially Gimli.
“Alas!” said Celeborn. “We long have feared that under Caradhras a terror slept. But had I known that the Dwarves had stirred up this evil in Moria again, l would have forbidden you to pass the northern borders, you and all that went with you.”
-The Lord of the Rings, The Fellowship of the Ring, Book II, Chapter 7: "The Mirror of Galadriel".
[Note: Celeborn later apologizes for his outburst and says that his words were shaped by his grief over the death of Gandalf]
Balrogs in general, and Durin's Bane in particular, played an incredibly important role in Legolas' life, and even more so in the lives of his forefathers. Many great Elves, including the High King of the Noldor, Fëanor, as well as Fingon and Glorfindel, were slain by Balrogs. Much of the First Age was spent in combat between Elves and Balrogs.
All of this would have had a significant impact on the young Legolas, Nd he would have grown up hearing about Balrogs frequently. They were among the few things that Elves feared, and were responsible for much sorrow and bloodshed among the Elves. Again, it would be more surprising if Legolas didn't identify Durin's Bane on sight.
As Legolas himself puts it:
"It was a Balrog of Morgoth," said Legolas, "of all elf-banes the most deadly, save the One who sits in the Dark Tower”.
-The Lord of the Rings, The Fellowship of the Ring, Book II, Chapter 7: "The Mirror of Galadriel".
Why wouldn't he recognize Durin's Bane as soon as he sees it? Nothing in the world is more feared and hated by the Elves, nor more dangerous to the Elves, except Sauron himself.
Consider the way Legolas breaks off the song he sings about Nimrodel and Amroth:
The voice of Legolas ceased. ‘I cannot sing any more,’ he said. 'That is but a part, for I have forgotten much. It is long and sad, for it tells how sorrow came upon Lothlórien, Lorien of the Blossom, when the Dwarves awakened evil in the mountains.’
'But the Dwarves did not make the evil,’ said Gimli.
'I said not so; yet evil came,’ answered Legolas sadly. 'Then many of the Elves of Nimrodel’s kindred left their dwellings and departed, and she was lost far in the South, in the passes of the White Mountains; and she came not to the ship where Amroth her lover waited for her...'
-The Lord of the Rings, The Fellowship of the Ring, Book II, Chapter 6: "Lothlórien".
From the song, and the story behind it, Legolas would have learned much about the Balrog in Moria known as Durin's Bane.
From Tolkien Gateway's entry on Nimrodel:
[The Elf-maid] Nimrodel had lived in Lothlórien since well before the Sindar and Noldor came. She was unhappy with the newcomers, as she thought they would bring the turmoils of Middle-earth to the golden forest. She lived separately near the river that would later bear her name, and spoke only her native tongue.
The only good thing she saw in Lórien was the Sinda Amroth, the King of the wood. She loved him, and he her, but refused to marry him. After the Balrog awoke in nearby Khazad-dûm in T.A. 1980, Nimrodel grew even uneasier in Lórien. She fled, and made her way to the edge of Fangorn Forest, but could not enter it.
Amroth found her, and promised her peace. Together they would travel to Edhellond, the port city in Belfalas, and thence set sail to the Undying Lands. They were accompanied by a small staff of Silvan Elves, including Mithrellas. All went well until they reached the White Mountains. The group became separated, and Amroth reached Edhellond well before the others. He decided to wait for his love aboard their ship.
When a storm broke loose and swept the ship out of port, Amroth leaped overboard, hoping to swim back to shore. But he was quickly taken by Belegaer's strong currents and drowned.
Nimrodel, in the meantime, had settled for a while at the river Gilrain, which reminded her of her home. She sat by the starlit stream and fell in a long deep sleep. After she woke, she journeyed further, but found no ship in Edhellond, and Amroth was long gone. Whatever she did after was lost to time.
And finally, we turn to the words of Tolkien himself:
"The Balrog is a survivor from the Silmarillion and the legends of the First Age. So is Shelob. The Balrogs, of whom the whips were the chief weapons, were primeval spirits of destroying fire, chief servants of the primeval Dark Power of the First Age. They were supposed to have been all destroyed in the overthrow of Thangorodrim, his fortress in the North. But it is here found (there is usually a hang-over especially of evil from one age to another) that one had escaped and taken refuge under the mountains of Hithaeglin (the Misty Mountains). It is observable that only the Elf knows what the thing is - and doubtless Gandalf." (Letter #144)
Note: A related question has come up - did anyone know that Durin's Bane was a Balrog, and when did they realize this? The answer is difficult to ascertain. "Ask Middle-earth" says:
It's never stated directly, but we can make an educated guess:
Though Gimli would definitely know about Durin’s Bane, it’s not really sure what he would have known about it. The dwarves wouldn’t have the same cultural memory of balrogs as the elves would. For them, Durin’s Bane might just have been understood as an evil spirit, a random dark creature that happened to live in their mine. It’s not unheard of in Middle Earth (I mean, what is the watcher in the water anyway?) And after a thousand years, that’s several generations of dwarves, who knows what history has done to that understanding. The only dwarf that really still took Durin’s Bane seriously at the time was Dain Ironfoot, and that’s only because he caught a glimpse of it during the Battle of Azanulbizar.
The elves of Lorien definitely knew that it was a balrog, but so many of them fled the area soon after, I’m not sure how common that knowledge would be there during the fellowship. Galadriel and Celeborn definitely knew, but they apparently never thought it necessary to inform anyone else. Also, this period (a thousand years ago, when the balrog woke up) is when Mirkwood stopped having regular contact with Lorien. So whatever version Thruanduil (and Legolas) would have heard about the balrog, it would have been whatever the dwarves that moved nearby told himm. As stated above, they probably wouldn’t have known it was a balrog, let alone have told the elves that.
And let’s not take those thousand years for granted. Even Gandalf wasn’t really aware of the balrog. He also knew of Durin’s Bane, of course, but when the balrog does appear during the fellowship’s trip through Moria, his reaction (“’A Balrog,’ muttered Gandalf. ‘Now I understand.’”) pretty much implies that he wasn’t expecting it. Given his time spent with Durin’s folk, he’s definitely heard the story of Durin’s Bane before. If he didn’t put it together, then I’m guessing the clues just weren’t there.
Basically, to sum it up, I don’t think anybody knew that Durin’s Bane was a balrog in the first place (except I guess Galadirel and Celeborn, who apparently like to keep secrets). Add a thousand years of murky memories and passing generations, and it’s not too surprising that nobody in the fellowship really saw that one coming.