Glad it is sorted out, but seriously this sucks.
Your DM has to remember that he is a player as well. He cannot tell people what to do. If he absolutely positively has to have a paladin of X in his group he has 2 choices. 1: ask really really nicely. With cream on top and no bickering about ACF's PF and allowed books. Or 2: play the damned thing himself as a DMPC (the horror)
On second thought there is a 3rd option. Think of a better plothook. Work for it dammit.
Actually if I were the DM I'd go with "4: you don't need paladin levels to be a paladin in an order of paladins, Lawful Good character with Favoured souls, clerics, crusaders, prestige paladins and a lot more as classes make perfect paladins, hell even a pure fighter could fit the role, it's all about the character behaviour and fluff, not so much about the class."