One problem is that if you wish to remember the fruits of Israel, why not take them? The Rambam (there) gives an answer (The items we take instead are easy to find; likely to maintain freshness in way grapes, for example, won't.) A better solution to this question is in Leviticus 23:40, where the plain meaning seems to be that any fruit (or better yet any foliage), from any stately or majestic (fruit) tree, ie etz hadar is acceptable for the fulfillment of the mitzvah.
And, indeed, in the time of Ezra, this appears to be exactly what the people did, taking the branches of olive trees (together with olive branches and oil tree branches and myrtle branches and date branches and branches of thick trees) in fulfillment of Leviticus 23:40.
Here's the passage:
"And they found written in the Torah that YHWH commanded through Moses that the Children of Israel dwell in Booths (Succoth) in the Seventh month. And concerning that which they heard [in the public reading] they passed a voice through all their cities and Jerusalem saying 'Go out to the mountain and bring olive branches and oil tree branches and myrtle branches and date branches and branches of thick trees to make booths, as it is written.' And the people went out and they brought and they made for themselves booths, each man on his roof and in their courtyards and in the courtyard of the House of God and in the broad areas of the Water Gate and the broad areas of Ephraim Gate."or in Hebrew
וַֽיִּמְצְא֖וּ כָּת֣וּב בַּתֹּורָ֑ה אֲשֶׁ֨ר צִוָּ֤ה יְהוָה֙ בְּיַד־מֹשֶׁ֔ה אֲשֶׁר֩ יֵשְׁב֨וּ בְנֵֽי־יִשְׂרָאֵ֧ל בַּסֻּכֹּ֛ות בֶּחָ֖ג בַּחֹ֥דֶשׁ הַשְּׁבִיעִֽי׃Notice something else? According to this passage the four species mentioned in Leviticus were used as materials for building a Succah. Note that according to Neh 8:15 using the four species to build a Succah is what is required because "it is written". In other words, when the people read Lev 23:40 they understood it to be commanding the taking of the "four species" for the purpose of building Succot. To this day, Samritans do just this, building their Succot from fruit and palm fronds. See here. Later Chazal would interpret Leviticus differently, and rule that we're to take the four species and wave them around, but Ezra's interpretation seems at least as reasonable, and it does have more support in the text.
וַאֲשֶׁ֣ר יַשְׁמִ֗יעוּ וְיַעֲבִ֨ירוּ קֹ֥ול בְּכָל־עָרֵיהֶם֮ וּבִירוּשָׁלִַ֣ם לֵאמֹר֒ צְא֣וּ הָהָ֗ר וְהָבִ֙יאוּ֙ עֲלֵי־זַ֙יִת֙ וַעֲלֵי־עֵ֣ץ שֶׁ֔מֶן וַעֲלֵ֤י הֲדַס֙ וַעֲלֵ֣י תְמָרִ֔ים וַעֲלֵ֖י עֵ֣ץ עָבֹ֑ת לַעֲשֹׂ֥ת סֻכֹּ֖ת כַּכָּתֽוּב׃
וַיֵּצְא֣וּ הָעָם֮ וַיָּבִיאוּ֒ וַיַּעֲשׂוּ֩ לָהֶ֨ם סֻכֹּ֜ות אִ֤ישׁ עַל־גַּגֹּו֙ וּבְחַצְרֹ֣תֵיהֶ֔ם וּבְחַצְרֹ֖ות בֵּ֣ית הָאֱלֹהִ֑ים וּבִרְחֹוב֙ שַׁ֣עַר הַמַּ֔יִם וּבִרְחֹ֖וב שַׁ֥עַר אֶפְרָֽיִם׃
וַיַּֽעֲשׂ֣וּ כָֽל־הַ֠קָּהָל הַשָּׁבִ֨ים מִן־הַשְּׁבִ֥י ׀ סֻכֹּות֮ וַיֵּשְׁב֣וּ בַסֻּכֹּות֒ כִּ֣י לֹֽא־עָשׂ֡וּ מִימֵי֩ יֵשׁ֨וּעַ בִּן־נ֥וּן כֵּן֙ בְּנֵ֣י יִשְׂרָאֵ֔ל עַ֖ד הַיֹּ֣ום הַה֑וּא וַתְּהִ֥י שִׂמְחָ֖ה גְּדֹולָ֥ה מְאֹֽד׃
More: Josh Waxman has a series of posts on Nehemia 8:13-18 and how the four species are understood there.You can read them here, here, and here.
Search for more information about [topic] at 4torah.com.