I feel your pain... I have several B&D 18v tools. 2 drills, Sawsall, chainsaw, and hedge trimmer.
I investigated getting my 2 batteries rebuilt, but the $70+ each at the local 'Batteries are Us' about gave me a heart attack! I priced their replacement battery cells and the price was almost the same.
Then I found a battery at WalMart for $40 and bought it. It wouldn't charge either so I took it back. Got a refund and found a 3/8" B&D drill kit in the same store with 2 batteries, drill and charger for $9 more than the bad battery alone.
There are several videos on rebuilding battery packs on U-Tbe, including this one:
http://www.youtube.com/watch?v=PtOS5evrqrQ.
If you can solder, you can do it yourself, just make a carefull drawing of how the individual cells are connected to get the voltage and current needed.
I gave in to buying new because of immediate need. There are several vendors on E-Bay selling the cells. Make sure you get the same type as what is in your battery or you risk damaging the chargers. Some say if you disassemble 2 battery packs, you can get enough good cells to rebuild 1. Good luck!
Chuck