I sure hope I'm in the right place...
Using a Radeon HD3870 that works fine under Windows (64-bit). After a supposed initial success using a pre-release version of KMS drivers (which may be a red herring), I have been unable to get 3D acceleration on any Ubuntu release from Lucid, unless I use a non-PAE kernel (I have 4GB RAM).
My Ubuntu bug ticket (including logs) is here: https://bugs.launchpad.net/ubuntu/+source/xserver-xorg-video-ati/+bug/574884
Another bug that looks similar: https://bugs.launchpad.net/ubuntu/+source/xserver-xorg-video-ati/+bug/657576
A similar looking bug with a similar workaround (which I'll shortly try on mine) on SUSE: http://web.archiveorange.com/archive/v/wmeLDauZzOL6SFQx1uKY
Could be the same issue as this: http://git.kernel.org/?p=linux/kernel/git/torvalds/linux.git;a=commitdiff;h=62fff811d73095bd95579d72f558f03c78f7914a
Original reporter hasn't responded to downstream information request in 2 years.