Sadly, I agree with the others to make a marriage event.
That doesn't fix the original problem though and that irritates me. Legacy SHOULD recognize that there was a previous marriage between the two and so there should be absolutely NO reason whatsoever that there is an error message.
Personally, I would report this as a bug, which you can do here: http://www.legacyfamilytree.com/Problems.asp
After all, they are completely separate marriages and so they are absolutely NOT events. This shouldn't be a feature request either as it is clearly a bug.