It is easier to re-stain before putting the new frets in, but it's not a big difference. Slightly smaller pincers make removing the upper frets easier, and putting a metal fret protector around the fret you are about to remove helps prevent possible damage to the board. Heating the fret up with a soldering iron first also helps in case glue's been used to stick a fret in and reduces the likelihood of chipping if it has.