What kind of video are you attempting to burn? What format is it in? What's the file extension? Where did you get it?
Video DVDs use a special kind of video format, which Express Burn attempts to convert your files to. The error encoding video message suggests that the software is unable to recognise the format your video is in (or your video is corrupt in some way).