Using Zoredache's excellent suggestions, I ended up processing each list in 3 stages, one for regular members and one for digest members, then a final pass to remove the old addresses. So, for each list I did this:
PATH=$PATH:/usr/lib/mailman/bin; export PATH
list_members --regular list_name | grep '@old_domain.com' | sed -e 's/old_domain/new_domain/' | add_members --welcome-msg=n --admin-notify=n --regular-members-file=- list_name
list_members --digest list_name | grep '@old_domain.com' | sed -e 's/old_domain/new_domain/' | add_members --welcome-msg=n --admin-notify=n --digest-members-file=- list_name
list_members list_name | grep '@old_domain.com' | remove_members --file=- --nouserack --noadminack list_name
The PATH statement is needed because the mailman binaries are in an uncommon directory (/usr/lib/mailman/bin on my Fedora system).