Whenever it does this to me, I will try removing the cable, waiting a minute, and plugging it back in. If that doesn't do it, I restart the phone and the computer.

Which OS are you trying to tether to? Have the option of tethering over bluetooth?