Don't restart unless you want to.
There are two clear options for this, and it's completely up to your preference (the current rules provide no clear guidance on this)
Simply allow them to change PCs. Write their old PC out and their new PC in. Bring the new PC in at the current level and if everyone else has a magic item, it might not hurt to let them pick one out (the current rules for higher level PCs involve no awarding of magic items, or more than basic cash, I expect fuller rules on this in the PHB).
Write in a class change for the PC. This might provide you with more story potential for you and your players. Work with your players to write a story where their character changes classes. Perhaps the cleric decides to go Paladin or the Wizard is struck with sudden inspiration and becomes a Bard.
The final option, and one I'm not including above because we know little of the mechanics and what the requirements would be (and as such we don't know if your PCs would even qualify), would be to let them multiclass. In this case they'd take levels of their other class and gain some of their low level abilities. Again, we don't know all the details of the 5e multiclass system, but we do know it involves level based MC like non-4th editions.
With whatever you decide to do, keep in mind that this is your collective story that you're all telling. Keep good communication between yourself and your players. If they want to play different characters, find a way to weave it into your story. There isn't a need to start over, unless you want to, that's totally kosher too. But don't feel like you have to start over simply because your players have decided they want to try out the fancy new classes that drop with the PHB.