You are letting Maya automatically change your weights. You cannot possibly expect a good result from that.
Sorry, but you will probably have to do one of the following:
a) redo your weights
b) check the weights that have more than 4 influences, and carefully clean them up.
Using the "prune small weights" or changing max influences or using "keep max influences" checked is generally going to give you awful, terrible results, and I do not recommend it.
To make skinning in Maya a lot less painful, you should check out ngSkinTools. It lets you paint weights using layers. By keeping different parts on different layers, it makes it easy to clean up issues like this with more confidence.
Maybe someone has a tool that is smart about reassigning weights, but I've never seen it.