I don't think the original poster has replied to this thread yet, have they???
Someone asked me about the possibility of doing this as a phone app about a year ago, but after extensive research I decided that I general purpose bird call identifier even on a smartphone with nice fast CPU and lots of ram and file storage, was not going to be an easy thing to produce.
I notice there is now an iPhone app that does this and is getting reasonable reviews, but the user has to edit the sound file so that the piece of audio that is to be analysed only contains the sound of a single bird with no background sounds.
So effectively they are using the massive power of the human brain to do a lot of filtering before the app even starts to analyse the sound.
On top of that, you need to have a large number of reference sounds, which you need to pre compile into a sound signature.
The arduino would need to perform FFT on the sound file, which it is do able, but as the normal Arduino only runs at 16MHz, its going to take it a lot lot longer than the 1GHz CPUs in smart phones.
For a general purpose bird call identifier a large number of bird calls need to be profiled, and they are to easy to source unless you are in that industry.
I.e you can buy sounds of major species for personal use, but there are loads of variants of each call that will not be included.
Also I was told my expert that juvenile birds make different sounds to adults, male and females can make different sounds, mating calls are different, and then there is general variability from bird to bird.
To be honest, I'd be surprised if the App that is on sale, works that well, despite its 5 star reviews;-)