Most PHB race can make an interesting Paladin- Humans for the bonus feat, Dwarves for their ability to wear armor and their Weapon Familiarity, Elves get their immunities and a dex bonus (so they get initiative, AC and ranged combat bonuses), gnomes or halflings could be good mounted Paladins and/or ranged attack specialists, and Half-Orcs get that brute force and RP style points.
As mentioned before Aasimar make decent Paladins.
Tieflings, like Half-Orcs, make for interesting Paladins to roleplay.
Half-Giants get to use oversized weapons, making them combat powerhouses.
Neandertals from Races of Frost have Str & Con bonuses, and lose Dex and Int- make a heavily armored but wise Neandertal Paladin and you have some of the force of the Half-Orc and few of the mechanical drawbacks.
Uldra, from the same source, are small with a Wis bonus.
Warforged- especially ones with Adamantine body- make fine paladins.
There are countless +0 to +1LA races out there- check out Planar Handbook, the various "Races of" books, Monster Manuals (Hobgoblin Paladin?), and Campaign sourcebooks.