Now I have no idea what is going on! Workgroups don't need to "exist" - putting a PC in one "creates" it, it isn't like a domain where there is a central authority to register with (and therefore "find")... sure you're not trying to add the machine to a domain rather than a workgroup? Its just a radio button option between the two in the same dialogue that you set the name....
Either way, to reset the whole thing, you can set the PC's workgroup name to something that has never been used before, click OK, allow it to reboot, then set it back to the LinuxMCE workgroup, OK and reboot again. Did you check your system event log for Computer Browser events confirming that the browsers are "forcing elections" when you change these things, or even reboot a machine on the same broadcast domain? There are segment browsers, master browsers, backup browsers, etc, and they all collaborate to compile a complete list of the workgroups and computers in the network... can get complicated, and it maybe nothing to do with the issue, but having them all talking correctly and able to find each other at a NetBIOS level will probably help when they are trying to confirm credentials (even if that is just guest, and there are no restrictions....)