This is an old question but I had the same problem today and was able to fix it by doing the following.
Locate the SMSE quarantine folder (default path is C:\Program Files\Symantec\SMSMSE\5.0\Server\Quarantine). This folder contains all the quarantined messages.
Make a copy of all the Q files within the quarantine folder (store the copy outside of the quarantine folder) then delete everything in the quarantine folder except for the Release folder. This will get rid of the “error when adding quarantine xml to dataset” message and any new message that are quarantined post deletion will show up ok.
From the copy of the quarantine folder you made before deleting the files you can locate the quarantined messages you wish to release by using the unique identifier number. Copy the message back into the quarantine folder and release through the SMSE GUI in the usual way.
This problem occurs because one or a number of the Q files within the quarantine folder have become corrupt. If you copy the corrupt file back into the quarantine folder you’ll get the same error message again.