I think your DM has a point. Clerics exist to serve their god and his ideals, a paladin exists to serve some abstract "good" idea. The cleric goals are much more well, selfish; as he does everything in the name of his god rather then by the aforementioned "good" cause.

On the other hand maybe if you take a cleric that doesn't believe in a god but rather in the abstract ideal of good and chivalrousness then maybe it could work...