Weight paint too sharp transition between affected areas
On another forum I finally got an answer!
The problem was that since I erased all weights from all bones to paint weights from scratch, all vertices other than the painted, had to be attached to any other bones. Basically one vertex needs to be attached to more than one bone.