How do I play HD video without it stuttering?

Try it on any other operating system with this specs and it will choke. Some Single Core 2 Ghz can't handle even 720p but 1080p it's a sure...

I have a PC: Athlon 3000+, Single Core 2 Ghz, ATI Radeon 4850 HD(1GB ; 512 bit) with big bandwidth and it chokes too... Overclocked to 2.4 Ghz and anyway chokes for 1080p(Blu-Ray).

Btw, try to compile the new kernel(2.6.38-rc4) it gives awesome performance boost(I don't know if it gives the boost for Single Core, for Multi-Core for sure but anyway, u may wanna try): https://wiki.ubuntu.com/KernelTeam/GitKernelBuild .If u want to compile the Kernel, don't forget that u need at least 7GB disk space.

My guess is the video is stuttering because it's trying to decode it entirely on the CPU. Even a fairly beefy CPU will have to work very hard to play a full 1080p video stream. GPU-accelerated video playback is much less taxing.

I have an Nvidia card using VDPAU with the proprietary driver, so I'm not sure what options there are for hardware accelerated video on ATI cards. First thing you should do is confirm your video hardware is even capable of video playback acceleration... models older than 2 years may not. Second, make sure you're using a driver that supports it - it's possible the ATI open source driver supports it even if the (better performing?) proprietary one doesn't. Lastly, you'll need a build of your media player software that is confirmed to make use of the appropriate video acceleration API - I recall that the mplayer in the repos for releases of Ubuntu before 10.10 didn't have VDPAU support, and it was a pain to track down which features that binary actually supported.

I googled "ati linux hardware accelerated video" (minus the quotes) and came across a few things, but nothing conclusive. Maybe an ATI user can chime in here with some help.

I would suggest editing the title of your question to be more descriptive, something like "Slow Blu Ray video playback on Boxee hardware".