If you have a DVD player, there is a DVD available that lays out some really good practice exercises (Elderly Instruments also has it in VHS). It's aimed at classical guitarists, but the exercises can apply to any style of guitar. It isn't an instruction video as such—not "How to Play Classic Guitar"—it's a collection of exercises and "calisthenics" for both hands, aimed at increasing speed and dexterity. It's by concert guitarist and teacher Scott Tennant, a member of the Los Angeles Guitar Quartet. It's called "Pumping Nylon."
Fear not. All of it should work for players of steel-string guitars as well, and if you can master most of the stuff he shows (you don't have to be able to read music—he demonstrates), there won't be much of anything you can't do on a guitar.
One of the things Tennant points out—and this is the reason I'm recommending it for Wil R's consideration—is that most guitarists use far more pressure fretting the strings than they really need to, and this can lead to all kinds of bad stuff, such as soreness and inability to free up the hand to move fast. Relaxation is the key! He shows you how to find out how much pressure you really need, and gives some exercises to get your fingers used to playing lightly.
Give it a shot. It might solve the problem. Or at least help.
Clicky. The Elderly Instruments blurb is not entirely accurate. The video runs 157 minutes, not 137.