It sounds me like a bandwidth issue on your user's end.
Presenter will support FLV or MP4 video (or will convert formats other than those two to FLV). Personally, I find that videos around the 720 X 480 resolution and 800 kbps bit rate seem to work best for my users. Consider that the video plays within a smaller section of the screen, so an HD resolution and bit rate may just be wasted bandwidth consumption.
I've not had any issue using MP4 videos, but it may be worth trying FLV to see if you get a better viewing experience. It is also worth clarifying how Presenter loads, which may allow you to change the setup of your presentation to better leverage the pre-loading function to prevent buffering.
Presenter loads the first three slides while you are seeing the loading screen. So if a video is within the first three slides, it may lead to a long initial load time. Once the first three slides are loaded and it starts playing, Presenter begins pre-loading an additional slide every three seconds. So, if your first three slides are short and the video is on slide 4 or 5, it may not have had time to pre-load the video before the user gets to that slide if they are on a lesser Internet connection. You may find that there is a better viewing experience if you put the video later in the presentation, or have longer slides before the video, to better allow the video to pre-load. Having a lower bit rate video will also help reduce the amount of time needed for pre-loading.
Thanks for the insight!
I'll give FLV a try to see if it helps. And, I'll keep the thread unanswered for now, just in case there are any other thoughts out there.