wuming79,
You are lucky to get a lot of good feed backs. If all doesn't work, then try this.
Apply soldering "flux" prefer "no-clean",many electronics components retailers carry it. If not, Home Depot has flux and solder also.
Well apply flux to both side of the board and touch one lead at a time, wiggle the cap to see if the solder joint gives, do the same to the other lead. Most caps are made of 2 leads (right?), work it one lead at a time.
In the extreme case where one lead of the cap is connected through the board's main ground plain(most of the time the negative - lead), apply flux to both side, use a heat gun (hair dryer is good enough) blow on the area of the cap (bottom side where the leads are showing), do not hold the heat blower close to the board, keep moving it in circle, touch your cleaned iron to the solder joints and if they melt instantly then stop blowing and start wiggling...
the cap.
Last, remember to clean the area with isopropal alcohol (regualar item in most drug stores), otherwise your board will be damage by flux's agents. if used "no-clean" flux then, you don't have to do anything.