The best part is that I don’t use Homegroups but, it’s nice to have everything working the way it is supposed to work.
How I did it:
The first step is quite drastic, and requires a complete fresh re-install on the machine where the Homegroup was originally created. This has to be done to eliminate as much as is possible of the old one.
Next, go to Homegroups and you will see a message about the old one but there should also be an option to create a new Homegroup. This is what I did, getting a new password along the way.
I then went to all of the other machines and joined them to the new Homegroup.
Voila, job done.. 🙂