Bike gears not shifting how they should
A rear derailleur moves two ways: the tension from the shifter cable will pull it one way (usually towards the larger rear cogs) and spring tension within the derailleur will pull it back when you shift down into the smaller cogs.

It sounds like the spring tension is not strong enough to overcome the cable tension / resistance when you're shifting.

If you had to replace other rusty parts, you can try oiling or just replacing the derailleur cable and housing.  If those are rusty or sticky, then your derailleur spring has to pull a lot harder to get things to move.

I have also had shifting troubles when the derailleur hanger is bent, causing the mechanism to swing the wrong way when I was shifting.  You can get a bike shop to check / straighten the hanger, or if you don't have a hanger (claw type derailleur) you can try to do it yourself.