I actually see a lot of potential for making Cleffairy Ash's starter.
Here's how I imagine the story going, from a good way, with Ash's opening being the same. Ash is late and Proffessor Oak has run out of all the Pokemon that he is giving away to trainers. But because he knows Ash and knows how desperate her is to be a trainer, he takes Ash up to Mt. Moon with him in his car to learn about the Cleffairy. He promises Ash that by the end of the journey, he will have his Pokemon. When they get there, neither of them can find any Cleffairy, or even how to get into the Mountains. that is, until Ash and Oak find a Cleffable flying over their camp site, letting sparkling stars glitter all around.
Ash and Oak find their way to the hidden village of the Cleffairy and Cleffable able discover the giant moon rock and are taken in by the Pokemon as guests to their festival, showing just how magical the Pokemon are, with their glitter dances and everything. But Team Rocket are there as well, who smoke out the cave and try to steal as many Cleffairy as they can. One of the Cleffairy uses its Metronome power to use Teleport, escaping Team Rocket and getting ash and oak to follow and help out in rescuing the Pokemon.
Oak wants to call the Police, but ash heads straight on, not thinking. Lucky for them, this Cleffairy wasn't the only one to use Metronome, and the trio are scattered all around, trying desperately to gather up the Cleffairies everywhere. Ash tackles them, but Jessie and James release their Pokemon again, Koffing and Ekans. Proffessor Oak shows up though with his Charizard and scares off the Pokemon. Ash asks why he wanted to get the police involved when he had a Charizard with him, but Oak says that Charizard is too old to fight anymore, like him, and that if Team Rocket had fallen for his bluff, he would have been at their mercy.
The episode ends (it could even have been a two parter) with the Cleffairy wanting to join Ash on his journey and the two of them setting off to challenge the Pokemon League. And later, the success of the game would inspire the release of Pokemon Pink, where you travel around the land with a Cleffairy traveling behind you.