It sounds like you don't have the codec for the movie your trying to watch. Movies are compressed different ways, and different methods need different codecs. If you go to microsofts website you can download the mpeg4 codec, which is what most movies are nowadays. I've attatched a codec pack that if you will install, you will never need another one.
As far as which program to use? I like GDIVX (Global DIVX) It does wonders on fullscreen.