Higher than 30fps is uncommon (usually 23.976, 25 or 29.97). If it is not smooth or is dropping frames then there's certainly a problem and I would not expect that CPU to manage AVC and VC-1 at HD resolutions and typical bitrates. MPEG-2 should be fine given the excellent decoding capabilities of the X800. The 3200 won't manage either.
I've got a P4 3.0E 1MB SSE3 and even overclocked to 3.6 with an X800XL it could not manage. However, replacing it with a 7600GT and utilizing CyberLink DXVA decoder (for PureVideo hardware) it can play the most demanding content I can find (AVC, 20Mbps, 1920x1080) even at 3.0 and at 3.6 only utilizes 65% avg so leaves room for multi-tasking. Whether it holds up to future potential disc content of 40-50Mbps is another question (likely MPEG-2, probable VC-1 but doubtful AVC). VC-1 is apparently broken on the Nvidia side at the mo' and dodgy on ATI.
So, if you can upgrade the CPU to something with at least SSE2 and even downgrade the CPU to a 7300 (or sidegrade to a 7600GT or 1650XT) then you're GTG. Otherwise you're SOL.
One SOL option, however, is to reduce the quality with a decoder such as CoreAVC or ffdshow by disabling standard in-loop deblocking and hope that lowers the demand upon the CPU enough for smooth playback.