If it's of any consolation, I've been fighting this same problem ever since I got my new Ubuntu box and 5850, with the naive hope I'd be able to edit me some HD video. 
I've installed the latest Catalyst (had to run it straight from the command line, any more detailed instructions to recompile it etc didn't work for me), as well as the splitted-desktop va-api drivers, to the best of my abilities.
vainfo:
Code:
libva: libva version 0.31.1-sds1
Xlib: extension "XFree86-DRI" missing on display ":0.0".
libva: va_getDriverName() returns 0
libva: Trying to open /usr/lib/va/drivers/fglrx_drv_video.so
Xlib: extension "XFree86-DRI" missing on display ":0.0".
libva: va_openDriver() returns 0
vainfo: VA API version: 0.31
vainfo: Driver version: Splitted-Desktop Systems XvBA backend for VA-API - 0.7.8.pre1
vainfo: Supported profile and entrypoints
VAProfileH264High : VAEntrypointVLD
VAProfileVC1Advanced : VAEntrypointVLD
Code:
display: :0.0 screen: 0
OpenGL vendor string: ATI Technologies Inc.
OpenGL renderer string: ATI Radeon HD 5800 Series
OpenGL version string: 1.4 (4.1.10428 Compatibility Profile Context)
I'm having a hard time understanding whether my new system is broken or not, since mplayer is now useless (internal data flow error for AVCHD.mts, audio but no video for most formats) but using vlc works just fine for everything. I wouldn't care about that so much, but I just can't get any of my videos into PiTiVi:
Code:
URI:00008-B8D63A89.MTS
Problem:An internal error occurred while analyzing this file: Internal data flow error.
Extra information:gstbasesrc.c(2550): gst_base_src_loop (): /GstPipeline:Discoverer-file:///media/Data/Media/Video/20090527_GrandmaCherryBlossomAidanBDay/00008-B8D63A89.MTS/GstFileSrc:src-file:///media/Data/Media/Video/20090527_GrandmaCherryBlossomAidanBDay/00008-B8D63A89.MTS:
streaming task paused, reason not-negotiated (-4)
Attempts to drag h.264.mov file onto PiTiVi result in a request for a missing "video/x-vaapi-surface decoder" plugin although this file format works in standard mplayer. 
OpenGL works fine. VLC playback works fine, with a bit of tearing. I've heard that mpeg-ts support in gstreamer is not ideal right now. It seems like "DRI" has been expunged from the system somewhere along the way, I suspect fglrx replaces it and the Xfree86-DRI warnings may be ignored, but I don't know for sure.
My feeling on the state of the art for my card from what I've been able to piece together from reading online is that va-api drivers just aren't there yet in terms of being able to stream all formats to gstreamer, and there's issues with the maturity of drivers for other video applications. I suspect I'd just run into a similar set of problems if I traded in my 5850 for a GTX-470/480 though as well. So just to add to the OP's questions, is there any way to proceed from here? Particular tests to run from the Phoronix suite? (BTW the Universe batch failed on something after Urban Terror, some 3D benchmarks wouldn't launch and I think it was lightsmark that froze my system)
Is the answer really wait for Natty? Anyone have a 5850 working as it should, and what does that look like c. Feb 2011? Thanks.