I think the audio is good, but I'm used to hearing French.
I think it is more often the lack of extensive practice of oral understanding that is the problem. All beginners find it difficult to distinguish a new language's all new sounds. Practice and more practice is the only remedy.
www.forvo.com is a good place to practice one's oral understanding.
Try to have your French friends on Duolingo on Skype, I'm sure they will understand you, or go on some site like Livemocha, or Busuu (but this feature is free only on Livemocha), and make some spoken exercice, some native will try to correct them. You will be sure to be able to make yourself understand in French.
It's important to remember that in French, generally speaking, the "s" at the end of words is not pronounced. Had it been "un menu" rather than "le menu", you would hear a "z" sound rather than an "s" sound. It would be pronounced like this: Nous avon zun menu This "z" sound is known as a laison, which appears is a situations where an "s" comes directly before a vowel. (Assuming you were speakinging quickly, the "z" sound would be spoken as if it was almost attached to "un" rather than "avons" in this situation.)
There is sometimes confusion over "le menu" because in English, we usually think of the menu as what the server gives you when you go to a restaurant. That is NOT "le menu"; that is "la carte". "Le menu" is menu in the sense of the series of dishes to be served (usually one at a time) as part of a single meal.