As mentioned above, trying to remove IC sockets is really hard at times.
If all the traces are only on the bottom then desoldering should be fairly easy. I say fairly with a large dose of salt.
You should be able to get away with a soldering iron and manual solder sucker. If the IC or socket is really bad then you can cut the thing out leaving enough go the leg protruding so that you can remove each pin at a time. Very time consuming to say the least, but for really stubborn ones it may be the only choice. You may need to use some flux and fresh solder on the pins to help the solder to flow. Also, a lot of these old boards you'll be working on have lead solder so if you're doing a lot, an extraction system or plenty of ventilation with a small fan blowing across your work area is a must. Don't be breathing all that in.
If the traces are on both sides of the board, then removing even the solder from the solder side it could still be joined on the component side. This is probably what is happening to you. this is where a desoldering station helps, though, again, it's not always the case.
If stuck DON'T try to force it as you'll pull the traces off the top of the board, and it's a real pain trying to fix. Check where it's getting stuck and concentrate on that pin. It might help to put the soldering iron on the pin, quickly remove it and wiggle the pin around the hole, hoping it doesn't solder itself back. It might help to solder the pin and remove the solder again.
In cases like this, and I want to save the chip I'm removing, I've a hot air gun I'll use. Remove whatever I can with the soldering iron, again using flux and fresh solder to get it started, suck as much of that solder up or use copper braid to help remove some of the more stubborn areas, then if stuck, use the hot air gun around the area that's stuck while pulling gently with an IC extractor or chip puller. The chip or socket should simply pull free.
Once out clean up any solder left around the hole, I'll typically use the copper braid for that, so you're left with a nice clean solder free area. Sometimes when the IC or socket has been removed you'll find a trace hidden underneath may be broken and was the source of the issue you have. Fixing traces is a whole other story.
Best of luck on the board, and once you know what you're doing, it doesn't get any easier

only joking, it does.