Only Dx10 class gpus can do full H.264 hardware decoding if im not mistaken.
With cpu decoding i can play 1080p in Windows 7, but with Ubuntu 10.04 i only get stutter with the same clip.
It depends on how the acceleration is implemented. For example, any card can decode H.264 if it has dedicated H.264 decoding hardware. Alternatively, the H.264 decoding can be implemented by using the GPU as a general-purpose massively-multithreaded vector processor. That can be done on any NVIDIA GPU starting with the GeForce 8 series. I don't know what the cutoff is for ATI. The Intel X4500HD chipset has H.264 decoding support (and will get Linux support for it soon), and I think GMA 965 and later GPUs have some support for VC-1, too, but it's not full decoding support, and it's not available under Linux.