A couple of days ago, I noticed that in both my and my wife's address book, all of the groups in Address Book had disapeared. It looks like this was caused by the Address Book sharing that I had enabled.
When I restored the data to a version that had the groups, as soon as the sharing process ran the groups got removed. This probably happened because I had marked this sharing to accept changes from the invitees.
When I disabled sharing, the problem went away. Since this happened recently, I think that Apple changed something on their .Mac servers.