Step 1: Background and Prep.
Then I went online and found 3300mAh sub-c NiMH batteries with solder tabs (these can be found at several battery suppliers, really the only important part is to get Sub-C size NiMH batteries of any reasonable capacity. Getting them with solder tabs makes it easy to make the final pack, so I advise them. I also found out that the stock charger has a reputation for wrecking the batteries, so I'm using my smart charger instead, it's a MRC 959 super brain charger.
Step 2: Battery Pack Assembly.
Given the position of the original packs leads, I used the 3rd and 4th battery as the ends, soldering #4's Pos pole to #1's neg. 1 then goes to 2, which goes to 3, which goes to the other terminal. Unfortunately I thought to take pictures only after I had assembled the pack with some clear tape. Also try not to short the batteries, they're usually shipped charged.
By the way use electrical solder with no lead in it. Lead solder is bad for you, and obviously you need to not breathe the fumes even with the good stuff. Check out the various soldering tutorials if you're new to it. Have aloe vera on hand, because sooner or later you're gonna burn something. Or wear welding gloves.
Step 3: Battery Pack Installation.
The only last part that was interesting was that I had to use dike clippers to cut out the fins on the inside of the battery cover, so it would close in the new configuration.
Step 4: Close It Up and Make the Wife Happy.
As shown here, you can see the charging paddle directly shorted to the positive lead by a loop of wire I also soldered in place. Tight confines, but I was able to do it with a bit of care. Lousy angle, but you can see the diode if you look carefully.
I'm basically going to let the dustbuster run down a bit with regular use, and as soon as I notice it getting slow I'll put the charger on it. This is probably an ok strategy with the NiMH batteries. It's still *very* strong now, and It's been about 2 weeks since it's last charge. It works better than it did new!