...In the text of LoTR, one would get the impression that Celeborn is a Nandor Elf who has never crossed the Misty Mountains.  Galadriel says something like 'he on this side of the mountains and I on that, and so we fought the long defeat.'  Galadriel herself was a late addition to the Legendarium, not appearing in the pre-LoTR versions of the Silmariallion. 
    But after the publication of LoTR Tolkien was impressed by the strong reaction that Galadriel elicited.  In particular, W.H. Auden, a famous writer whose review still graces the inside cover of the Ballantine paperback, told Tolkien that she reminded him of the Virgin Mary.
     After that, nothing was too good for Galadriel.  Her origional backstory - that she was an unrepentant rebel - was downplayed, and the official line was that she was utterly pure, merely following the rebels because somebody sensible had to keep an eye on Feanor. 
    As Galadriel's status rose, so did that of her husband, though in a sort of lefthanded way.  I like to joke that Tolkien fell in love with Galadriel, and so minimized Celeborn out of jealousy.  In any case he became Sindar, a relative of Thingol Greycloak.  Even this was not good enough; in another version, he becomes Teleri, still related to Thingol, but a High-Elf in his own right.  In this version he is the son of Galadhon, the son of Thingol's brother Elmo.  This would make Celeborn Thingol's great-nephew.  He's also very old - perhaps older than Galadriel.