I've had a similar problem it turned out that it was completely unrelated to the complexity of the brush but rather it was related to the texture information. Try resetting all the texture information on the map and try again. that's what fixed it for me once.