When you are creating the preset, are you making any changes on the Toolbar Tab?
so far the only way I have been able to recreate the problem is:
1- Open the preset manager (Insert -> Preset Manager)
2- Select HTMLEditor Presets form the Product Select List.
3- Click New
4- On the toolbar tab Leave the Default toolbar selected and click the minus button til all of the toolbar options are removed.
5- Click OK and save it as a new preset.
This creates the empty toolbar preset and generates the "Toolbar 'Custom' does not exist!" error message.
If I do not remove all of the toolbar items, I do not get the error.
can you list the exact steps you are taking to create a preset so I can try to recreate the problem.