I killed my entire party about six months ago - first time for me, too, and it happened only because the players had been unbelievably, sleepwalkingly stupid. In short, they waded into battle with a master villain right after repeated unsuccessful attempts to find out "what exactly that shadow was doing there behind that urn, let's go look once again". There was no one in that low-level group who wasn't heavily Strength drained.
When that fateful battle with the master villain ended, we sat around the table for a while, stunned.
Then slowly we started making new plans. Like you, bolen, I was already secretly counting on having three more undead opponents for the "revenge group", but I asked my players whether revenge appealed to them. As it turned out, all of them preferred a fresh start , so I went with that.
At any rate, their common "death experience" is adding more depth to the new game ... not to mention considerably improving party combat tactics.
I like Henry's suggestion myself, but I wouldn't recommend it if your players got their characters killed because of raw stupidity (and your account sounds like they did). Gives them the wrong sort of signal.