Ok, I tried to follow your steps and the same message appears to me, but I think it's a problem of PowerPoint (I think it was made only for uncompressed videos, or only to let you add a button with a cinema-camera drawn on it).
You have at least 2 solutions to this inconvenience:
1. When you create the hyperlink, you may try to use "Start program" instead of linking the movie directly into PP. This way you can start BSplayer (or another player) and reproduce the movie through command lines
2. (I found this solution by searching the Help on line of PP) Select "Object" from the "Insert" menu item.
Then select "Multimedia clip" and be sure the "Create new" option is selected. Press OK. From the "Insert clipboard" menu item choose the first option (Video for Windows...) and then select the file you want to add to your slideshow. To play it simply press the Play button on the multimedia toolbar (just below the menu). If you want to place the clip in a different position, then click outside the movie region and then drag it everywhere you want to.
Note: when you add a movie as an objects to your slideshows you can't add it to a custom animation.
If you want to find these instructions by yourself in PP, press F1 in PP and search for "Solve problems related to movies".
I hope this helped you
