On the desoldering braid thing, yes you have to be careful not to scorch the fiberglass underneath the trace, or it can lift. Another trick for keeping traces intact is to make sure the solder is fully heated before applying force to the joint. If the solder is only warm but not freely flowing, the trace can give way before the solder will. This can happen when you're re-heating solder joints to push components down closer to the board: don't push on the component until the solder is flowing freely.
Also on the braid, yes, you will only pick up a portion of the joint's solder with each wicking. You may need to use up to an inch of braid to completely desolder a joint, if you did a sloppy job of soldering.
On the caps issue: yes, bigger is better, but only in the same way that it's better to walk into a store with a million dollars than to walk in with only $10, when you intend to buy $20 worth of stuff. A little reserve on the voltage is okay, but there's no need to go overboard. If anything, you might want to increase the capacitance of the power caps (not the signal caps, though!) but again a voltage reserve is only a minor nicety. I think cmoy's article overspecs the caps already: it calls for 100V caps in places, yet there's no way you'll even approach that voltage with a pocket amp.
What can you do? You can try desoldering the caps and then soldering new legs on, bending them over and soldering the new legs into the holes. This is tricky because you often end up heating the legs enough to melt the leg-to-leg joint as well. It may be better to solder the new legs in separately, then solder the caps to the legs.
Also, if you have more than 2 millimeters of stuff sticking out of the bottom of the board, just use your nippers to trim things down. You want that surface to be relatively smooth anyway, especially if you're using a metal case, because sharp stuff on the bottom of the board can pierce the insulation you have on the bottom of the case. See this thread on HeadWize
for pics of what your board underside should look like.