bbrown,

First thing I would try is cycling your suspect batteries a few times. If you don't have a cycler, you can do this with your wall charger a stopwatch or timer and some patience. Fully charge your batteries overnight for at least 18 hours. Then turn on your transmitter and start your timer. When the low battery alarm goes off, note the time. As previously noted, this should be in the range of 3 - 4 hours. Repeat this procedure and see if there is any notable difference.

Cheap Battery Packs will make replacement packs and they are great to deal with. They have 5 different types of cells that they can build that pack for.
http://www.cheapbatterypacks.com
Select Super Listing, tx, Futaba, flat style (verify this on your transmitter but I looked at mine),

If you stay with NiCd you can stick with your wall charger. Any other cell chemistry will require a more exotic charger.