You could always buy some new cells and solder it up yourself, I did that with one of my drills. Got the pattern slightly off, though, and had trouble getting the battery pack case back on. I'd do it again though, REALLY saves on cost for not having to pay some of the extortion-like markups on proprietary battery packs.
Take it apart and see if it's just a bunch of C-cells. You can buy cells designed specifically for use as battery packs that come with solder tabs pre-connected.
Of course, last time I did this it cost $35 in just batteries, and this was a lowball website selling for around wholesale, so that repacking guy sounds like a great deal- almost too good to be true...
Edit, I think your link should be:
http://www.voltmanbatteries.com/ [This message has been edited by SteveFehr (edited 07-30-2006).]