I'd allow it.
It does break the type of a pure paladin, however. One who is devoted to his Righteousness above all else (your guy is also, at least in part, devoted to his music). It also breaks the type of a bard, one who is dedicated to versatility and flexibility (your guy is narrow in focus, singing hymns and crusading for his deity).
But there are a few other ways you could achieve the character as well, if you have a stringent DM.
1) Mutliclass cleric/bard. Take the War and Good domains, or perhaps, if you can find a Song domain anywhere, take that instead of Good. Have a song for any verbal component in a spell. The hard part here will be armored arcane casting -- I'd spend a few feats to reduce the penalties (I'd say you could reduce the spell failure chance by about 10% with one feat, stackable). Not sure if Monte's bard would have that problem, since I don't have my BoEMII here.
This is doable, it just means that you can be a crusading singer who isn't in the heirarchy of official paladinhood, due to your lack of focus and exculsion of all else. I'd let him be Neutral Good, just have him think of his church as the greatest good. He's obedient to a fault -- he can't *just* devote his life to his god, and so he's unfocused.
2) Bardesque PrC for paladins. This requires a bit more DM intervention, but has the benefit of giving you nearly *exactly* what you want. Be just a paladin for a few levels (enhance the flavor -- his laying on of hands is accompained by a song of praise, his smite evil is with "Onward Heironian Soldiers" in the background. Take Perform as cross-class, and maybe even Skill Focus in it...). Then, design a PrC that casts bardlike spells without it being arcane (no armor failure), with a more specially designed skill list (probably without rogue skills, but with cleric skills...I'd think about 4 Skill Points/level would be enough). The Bardic Music can be extrapolated no matter what the class, because it goes by ranks. Bardic Lore can be done no problem as "Religious Lore," and be limited to items involving your church in some way or another. Maybe even add a few different uses to Bardic Music (one that gives you Fast Healing for as long as you play, or one that serves as a negative effect on evil creatures/unded). It lets you narrow your focus without really sacrificing anything you wouldn't want anyway...makes the extra baggage useful.
3) Be a NG bard for a few levels. Once you have a decent repotoire, have a calling and narrow your focus to the Paladin for a few more. If you ever get all the paladin abilities you want, you may want to finish up your 20 levels as a Cleric, or go a bit into Cleric before you dive into Paladin.
This is purely by-the-book. You'll retain every bardic ability you've ever had regardless of what you do in the future -- you retain them. If you cease to be a Paladin, you still retain your Paladin abilities as long as you act like one (you only loose paladin powers if you do something evil, stop being Lawful Good, or grossly violate the code...you can multiclass, you just can't go back, just like with the Bard). And then you cna finish up as a Cleric if you want some more divine magic. Or, if your DM insists on more rationalization, go into a Cleric before you go into Paladin. Gives you time to change your mindset from NG to LG, and you can only loose cleric abilities if you offend the god -- probably not happening if you become a paladin.
This would also fit your story pretty well. He first was interested in the music (Bard levels), and then was awakened to the power of the god (Cleric levels), and then decided to pick up the sword against evil (Paladin levels).
--END--
I'd personally encourage you to go the Prestige Class route, since that lets you keep the most flavor in your character while only making you a slightly off paladin for a few levels -- more music than martial. I wouldn't mind if you went just for a pure mutliclass though, since classes will always be to me just lists of abilities, and there's no mechanical reason for the alignment restrictions. And if you're DM's a stickler, you'll have to stretch his story out a few levels so that *eventually* he becomes the archetype you envision. You also have to plan those levels pretty carefully, down to the exact level you want to give up/get certain classes.
It's doable, but with the flavor restrictions in place, it's a bit awkward. I'd say you justified a crusader with song powers pretty well. The best way to emulate that, IMHO, is with a Prestige Class ("Member of the Heavanly Chorus" or something), since the Bard carries a bunch of extra baggage, being the jack-of-all-trades. It's not exactly a paladin/bard per se. It's a paladin with song magic. Cool image, so let's make some abilities to fit it in a PrC rather than bending rules for a character who won't exactly be optimized.
That's my DMing style, though. I'm very linient, I've been told. My players seem to have fun with it.

But, yeah, for a simple answer: I would allow that character, with the stipulation that I would advise it to be better realized through a PrC than a mutliclass, but if you/your DM doesn't want to devote the time to developing a PrC, the mutliclass paladin/bard works good enough for me.