Depending on the price of the servo, it's often more economical to replace the stripped gear (and it sounds like on of yours could be stripped) than to replace the servo.

If you got the servos from Tower, look them up in their online catalog. On the tech info page will be mention of replacement gear sets if any are available.