Hi Wolfman,
I had exactly the same problem as you a while back. After re-installing windows, I had the same message given.
I'm pretty sure that you will find that the dvd decoder program (win dvd, intervideo dvd, etc) is not on your windows recovery disk. Check all the disks that came with your laptop, and hopefully you will find a "utilities" disk. This usually has manufacturer specific programs (power saver, dvd progs etc).
Hope this helps
419