I don't know about VLC, but in MPC go to Options > Playback, enable 'Change fullscreen resolution' and set it to 1280x800 32bpp 60Hz. Or check the video's properties to see what resolution it was saved at, then make the appropriate changes in the media player to match the video's resolution.
Have you installed the
AMD Dual Core Optimizer? This is to correct timing problems with dual core AMD CPUs. It might not be relevant to this problem, but it's advisable to install anyway.