If you give paladins sense motive as a class skill instead of detect evil, you should also give them more skill points so that they can make use of it. A class with 2 skill points/level that needs every stat except intelligence (and, to some extent, dexterity) doesn't get too much milage out of extra class skills.
OTOH, I agree with Hong's implied judgement in the last post. The rules for detecting alignment evil/good/law/chaos are useful to players but any DM with a nuanced understanding of how alignments work can keep characters from drawing too many conclusions based on the kind of alignments that should be showing up in an intrigue game.
For example, when paladins in my game detect evil in a city, they almost always come up with a positive somewhere in their 60' cone. (Which usually penetrates buildings' walls too). "You sense three sources of evil. . . One is behind the tavern wall, the man with a scar through his eye practically feeling up the prostitute in the corner, and the halfling in front of the fire. . . Moderate, weak, moderate."
As a player frequent player of a paladin, I've learned to interpret those results as well. The moderates could be weak evil outsiders, moderately powerful undead, secret cultists (clerics) of evil deities, or simply people who've survived a few dozen years by cutting corners, cheating and exploiting people. It's not a license to smite and it doesn't mean that they're the people I'm looking for. Strong and overwhelming evil are another matter, but it's pretty hard for non-clerics to register as either strong or overwhelmingly evil.
In fact, say I were looking for members of a secret, evil organization like the Sanguine Kris. In general, I'd expect 1/3 of the people I meet to register as evil of some kind or other. In a corrupt, intrigue-ridden government, I'd guess that at least half the people I'd be dealing with would be evil. So, detecting evil wouldn't really narrow the field down too much. If the Sanguine Kris were composed of rogues, assassins, mages, nobles, etc they'd look like all the rest of the corrupt officials and nobles. If they were composed of (or even contained) priests and blackguards--the kind of people who would radiate unusual evil, they would probably have undetectable alignment, misdirection, and non-detection (and, at higher levels, mind blank) up all the time so focussing my investigations on people who registered as evil would actually make me less likely to find them.
To make matters more difficult, those magical protections would be so common in a corrupt, intrigue filled millieau that I wouldn't be able to investigate everyone with that kind of magic up either--after all, if detect evil, detect chaos, detect thoughts, zone of truth, and detect lies existed in the real world, how many politicians, CEOs, union officials, and activist group leaders would not invest in misdirection, non-detection, mind blank spells, or other such defensive measures? (Still, a lowly scribe, minor functionary or bookkeeper who radiated abjuration magic would be a suspect--but that's the kind of thinking I'd expect to be desirable in an intrigue filled game: "Thantinius Bookworm the assistant secretary to the director of the hall of records radiates magic indicative of a second or third level abjuration spell and wears a valuable ring that radiates magic too. That's unusual for an assistant secretary--what's he trying to hide? And where did he get the kind of money to afford such protections? Maybe he's not what he seems; I think I'll look at this more closely."
