This sounds like you might have a cache problem.
In that case, the contacts didn't changed group actually, it is just that Messenger wasn't able to get the group information from the servers at this time or that something is conflicting in your cache.
Only when it doesn't solve itself after a few days, I would manually (there is no other way) move them all back.
What you can try in the mean time is deleting your contacts cache:
1) completely close Messenger (right click the tray icon and choose 'exit').
2) Remove the directories:
\Documents and Settings\
your_username\Local Settings\Application Data\Microsoft\Windows Live Contacts\
your_windows_live_id\
\Documents and Settings\
your_username\Contacts\
your_windows_live_id\
Note: some directories might be hidden, so make sure you have enabled the viewing of systemand hidden files in Windows Explorer's options.
It is worth a try as it wouldn't harm anything. It only might take a bit longer to log in the first time after you did this.
EDIT: EBFL, did you by any chance put something in your PSM (
see here)?
/ 
