Mpeg1 is the safe format for video playback on just about any post 1990 machine. I suspect a codec problem.
There is a small utility called Codec Finder 5,1 that should be able to identify the video compression. Its Freeware and available at
www.vnunet.com/vnunet/downloads/2128894/codec-finder
It is then a question of establishing whether the codec required is missing from the problematic computer. I'm afraid I have no idea which codec Nero uses.
As an alternative you could simply load the offending video into Premiere(it won't be harmed) and save as or export it in MPEG1 format and try that in your publication.
Let us know how it goes