Do you actually have to paint the fractal? I mean couldn't you compute the visual element in a buffer then just paint and image off screen?

Alternativly what is your painting code like? are you forcing a repaint on the entire fractal? or just the visible or dirty regions?