First, only try adjusting with a slack cable. On the rear, shift into your lowest gear, quit pedaling, then shift into your highest gear. This will give you maximum slack. On the front, it's opposite.
Often an adjuster will seize onto the housing end. When the cable is slack, try pulling the housing out of the adjuster and be sure this isn't happening.
Then try loosening the adjuster. It should be able to thread all the way out. Inspect the threads for corrosion and damage and repair as needed.