That question is explored in this article on the BBC's website.
In the months before 9/11, the Taliban brought world attention to their extremist brand of Islam when they threatened to destroy the statues of Buddha that were carved into a mountainside in Bamiyan, Afghanistan. The threats caused an international outcry and a call by many to save a historical and cultural treasure. It also thrust into the limelight the bigoted and intolerant form of Islam practiced by the Taliban, which denounced the statues as being "un-Islamic".
But despite the pleas from around the world to save the statues, the Taliban went ahead on March 21, 2001, and destroyed them. Interestingly, according to this entry in Wikipedia, Taliban leader Mullah Omar initially wanted to protect the statues, but he claimed that when foreigners came to him and offered to repair the statues, he was offended because there were people starving in Afghanistan and that money should instead be spent on them rather than preserving pagan statues.
I shared the disappointment of many at the time when the Taliban destroyed the Bamiyan Buddhas. It was an act of cultural vandalism against works of art that were relics of an earlier time in Afghanistan's history before the advent of Islam. Just imagine if Islamic hardliners tried to destroy the Sphinx in Egypt or if anti-Christian fanatics dynamited the Christ of the Andes statue on the border between Argentina and Chile. However, I remember some voices at the time pointing out that the international attention over the Bamiyan Statues overshadowed the appalling treatment of women under Taliban rule and that this was where the real outrage should be focused.
As for the question of whether the statues should be rebuilt, I personally would say no. For one thing, the rebuilt statues would not be the statues that were previously there, just replicas. They would not be authentic. Secondly, it would fly in the face of everything that Buddhism purports to be about. The central message of Buddhism is that it is our attachment to the things of this world that cause us to be unhappy. The Buddha himself would likely say that the statues were material objects, and now that they are gone we should just let them go. Lastly, the empty recesses themselves can serve as a monument, a monument to intolerance and cultural vandalism.