I agree that the Paladin always felt like an extension of the Fighter in QfG. I never really thought of it as a class on it's own.
I can see the Bard as fitting into the 4th mold well, maintaining a distinct identity from the other 3. Charisma, communication, and the knowledge of music and mood could take this character far.
I also see what you're getting at with the songs and spells. That could indeed be an issue. Perhaps each song could be played on a variety of instruments, or in a few different keys, and you'd have to choose the right combination to achieve the necessary tones. Play a bad note and risk death! Just a thought, but I'm sure you've got plenty of your own.