for a,b in zip(alist, blist):
    msg = b.join(msg.split(a))

for a,b in dict.iteritems():
    msg = b.join(msg.split(a))

どっちのほうが速いかな？
iteritems() はあまり速くない印象があるけど…