Translation:He said that we had lost a friend.
Correct, "that" is frequently optional in English as a conjunction, but sometimes it is certainly required as in, That book is high up on the shelf. Just a reminder. In this lesson, "...that we had..." it is optional, but be careful, "that" is not always optional in English. :)
"un amigo" is not specific enough for the personal a, so it is not used in this sentence. In a different sentence, "a el amigo" would work or "a Pablo". http://spanish.about.com/od/prepositions/a/not_personal_a.htm
Audio: hearing "cabiamos" does not really make it terribly easy to decipher that it's actually "que habíamos." 4 syllables instead of 5. Maybe a long-time native speaker can glean what's actually being said, but even knowing what the verbiage is, I cannot hear "que habíamos" in the audio.