Galadriel and Celeborn are a strange couple, that's sure. But is there some reference to the reasons why Celeborn doesn't leave for the Grey Havens (which he will do, sooner or later even if we don't know when) together with his Queen?
You're right that we don't know exactly when he did leave:
It is said that Celeborn went to dwell [in Rivendell] after the departure of Galadriel; but there is no record of the day when at last he sought the Grey Havens, and with him went the last living memory of the Elder Days in Middle-earth.
However Celeborn probably stayed to ensure the success of his new Elven realm, East Lorien. Elves also only left when they were tired of Middle Earth. In Celeborn and Galadriel's case, it appears that the wife tired before the husband, though it was not unusual for Elven partners to spend years apart (see Elrond and Celebrían).
Celeborn and Thranduil met in the midst of the forest; and they renamed Mirkwood Eryn Lasgalen, The Wood of Greenleaves. Thranduil took all the northern region as far as the mountains that rise in the forest for his realm; and Celeborn took the southern wood below the Narrows, and named it East Lórien; all the wide forest between was given to the Beornings and the Woodmen. But after the passing of Galadriel in a few years Celeborn grew weary of his realm and went to Imladris to dwell with the sons of Elrond. In the Greenwood the Silvan Elves remained untroubled, but in Lórien there lingered sadly only a few of its former people, and there was no longer light or song in Caras Galadhon.
All quotes from the Appendices.
When the Great Ring was unmade and the Three were shorn of their power, then Elrond grew weary at last and forsook Middle-Earth, never to return.
From this it could be inferred that the Ring bearers were specially wearied by the destruction of the Ring and the loss of their ring powers. So it could well be that Celeborn, not having bore a Ring, was relatively less wearied and could endure remaining the Middle Earth for a bit longer.
It could also be that since he never saw the light of the two trees he didn't have the longing that Galadriel had to return to Valinor. He had been in Middle Earth for a very long time.
On the Elven scale of life, it wasn't that long a time apart. He was a Sinda, so he loved Middle Earth, and didn't really have the longing to go to the Blessed Realm that Galadriel and the other High Elves did. He probably went maybe fifty or a hundred years after Galadriel, which, considering she is well over 7,000 years old, is like nothing.
Elvish flaws were akin to human flaws, but not identical. Being undying, Elves seemed often to display the defect of wanting to preserve a world free of defects in a larger world fraught which with them. This is the basic theological problem of the Three Rings... Not a terrible problem, but still, a desire contrary to life as it has now to be lived in Middle Earth: the timelessness and changelessness of Valinor are simply not meant to be had, or to be desired, in our human home.
Galadriel learns this when she is tempted with true power to preserve, and says,
"I will diminish, and go into the West, and remain Galadriel."
Celeborn (apparently) did not leave Valinor for the reasons his wife did - and relative age aside - he has not suffered as much the diminution of self that comes with the desire to preserve things unchanging. He will so suffer now... And I suspect will depart not long after Elessar's death.