Yes, any sort of major replacement needs Photoshop. Takes a lot of practice. Are you dragging the brush, or just making a lot of static pokes? Dragging + wiggling is good technique.
Another technique is to duplicate the image layer, then shift one of the layers a few times the width of the line, diagonally is best. Then create a mask on the top layer. Brush black on the mask over the area you want to de-wire, causes the "clear" area below to show through. I still like the rubber stamp, however.