This is a very strange traceback. I can't imagine how it's occurring frankly, since pickle *should* have protections against recursively linked objects, and there shouldn't be any such objects in the metadata (a dictionary with simple key/value pairs) or in the Message object.
Does this still occur with the beta1 or the latest bzr trunk? If so, please re-open this bug and attach the offending message, and I'll try to reproduce it locally.
** Changed in: mailman Status: Triaged => Incomplete