What capacitor exactly you are trying to replace? Is that the electrolytic or the ceramic capacitor?
My guess the reason why you can't melt them it's because the soldering iron you use has an oxidized tip try to clean it first and apply some flux before you solder the capacitor.
If it does not help you will need a BGA hot air to help to melt them out.
The Aluminum Solid Capacitors there was three in a row and they all bent and broke. Thanks, I'll clean off the tip, get some flux and try again this weekend.