Who could have been a good VP for Lieberman? He'd need someone close enough to him ideologically to be cohesive but with enough differences that he can expand his appeal, particularly to the more liberal part of the party. John Kerry maybe? That's pretty New England heavy though. And as Joe is balding and grey it would help to have someone young and energetic looking, but I can't see John Edwards as a good fit.
It would have been Kerry or Clark, clearly a national security democrat, but I would have preferred Gephardt-Kerry than a Lieberman-Clark ticket.