I can imagine a slight amount of anxiety back when CARD CATALOGS were commonplace and one had to understand the indexing system (the dewey decimal system), scribble down the numbers onto slips of paper, hand them to a surly librarian and then wait and wait.
So as far as I can see, there is no real excuse except "I'm not used to books because they're not the Internet".
They don't know the exact book they need. That's where things go south. Any idiot can type the title into most library search systems now. The problem students have is when you ask something that requires them to figure out which books they should look in themselves.
Me neither (probably doesn't help that I'm a trained librarian). I love walking into messy used bookstores too, where the books are piled precariously high and and stuff everywhere. I wonder if there's a 'used-book store anxiety'?
Although having said that, I can absolutely empathize with a library that big being confusing (especially when parts of it are spread all over town). Thankfully, our university library provides short introductory courses on how to use a research library, and there are brochures lying around everywhere that cover the fundamental stuff.