First up, the RAW. This is pretty simple: Divine Sense works on celestials, fiends, and undead. Player characters are all humanoids (see page 11 of the PHB), and the Tiefling traits do not say anything about making the character a fiend in any way.
Next, we have the lore. In 3.5e, tieflings were the descendants of actual fiends, whereas in 5e, they are simply a race that has had the essence of Asmodeus infused into their bloodline. So they're a bit less fiendish than they used to be. If we look at the fiend type in the Monster Manual, it says that
Fiends are creatures of wickedness native to the Lower Planes.
Tieflings definitely don't fall under this category lore-wise, because they are a humanoid race native to the Material Plane.
Trying to argue that abilities that work on fiends should work on tieflings is like trying to argue that abilities that work on dragons should work on dragonborn, but what you have to remember is that fiends are the physical embodiment of evil. The differences between tieflings and real fiends are insurmountably greater than the differences between dragonborn and dragons.
The taint in the tiefling bloodline is a devilish one, so if they were fiends, they would be devils. Taking a look at the description of devils in the Monster Manual, we see that
Devils personify tyranny,
and that
Devils live to conquer, enslave, and oppress.
The fact that tieflings are allowed to be any alignment contradicts this, and similarly, tiefling characters are allowed to do things other than conquer, enslave and oppress - they're definitely not devils.
Finally, if another argument is needed, Jeremy Crawford agrees that tieflings are humanoids, not fiends, and can't be sensed by a Paladin's Divine Sense.
