The update/Patch 4 shouldn't matter for Majesty, that is just bug fixes and hero adjustments.
So while it's unclear from your original post if it played successfully on your same laptop, with just the OS changing from 8.0 to 8.1 as the only difference, it sounds like the intro video may be having problem playing.
First, was there a display option when you installed Majesty? It can only be run at 800x600.
Second, can you edit the shortcut so that it has -nointro at the end of the shortcut patch?