Throw the Ni-Cads away they suck Get some Ni-MH's they last alot longer. Get the Highest milliamp/hour you can find, Mine are 2100 mAh
There is nothing wrong with NiCd batteries other than NiMH batteries are 'better'. Keep in mind that the "voltage points" for NiCds are different than they are for NiMH batteries. In other words, the voltage settings for low battery are different between the two technologies.
I know there is some debate on this topic, but for as long as I can remember, people would always fully discharge NiCd batteries before recharging them to mitigate their "memory effect". You do not have that problem with NiMH batteries. Actually with NiMH batteries, you do NOT want to discharge them below 0.90 volts per cell.
Lastly, I totally disagree that you should get the highest capacity NIMH batteries possible. The higher capacity batteries are more likely to just fail, and they will not last as long in terms of months. I know others are going to debate this issue too, but what must be considered is the actual capacity of the battery after some use, not what is on the label.