Well I posted a thread on the steam community forums with a good deal of info for issues on both 12.10 Quantal Quetzal and 12.04 Precise Pangolin (both 64-bit versions):

http://steamcommunity.com/app/221410/discussions/0/864957912614875330/

My card is a Radeon HD 4890.
Basically these are the current issues:

On 12.10, the official 13.1 legacy drivers don't work on the 3.5 kernel and 1.13 xorg, and using a modified driver from a custom PPA churns out subpar performance, with no anti-aliasing without a crash.

On 12.04, the drivers from the 'Additional Drivers' app in the OS give this problem: http://steamcommunity.com/app/221410/discussions/1/882966057052333152/
Resorting to the official AMD 13.1 legacy drivers from their webpage makes my system sluggish and makes Steam hangs when starting with the following output in the terminal:

Running Steam on ubuntu 12.04 64-bit
STEAM_RUNTIME is enabled automatically
Installing breakpad exception handler for appid(steam)/version(1360621458_client)
SteamUpdateUI: An X Error occurred
X Error of failed request: BadRequest (invalid request code or no such operation)
Major opcode of failed request: 139 (ATIFGLEXTENSION)
Minor opcode of failed request: 66
Serial number of failed request: 13
xerror_handler: X failed, continuing
SteamUpdateUI: An X Error occurred
X Error of failed request: BadRequest (invalid request code or no such operation)
Major opcode of failed request: 136 (GLX)
Minor opcode of failed request: 19 (X_GLXQueryServerString)
Serial number of failed request: 29
xerror_handler: X failed, continuing
SteamUpdateUI: An X Error occurred
X Error of failed request: BadRequest (invalid request code or no such operation)
Major opcode of failed request: 136 (GLX)
Minor opcode of failed request: 19 (X_GLXQueryServerString)
Serial number of failed request: 40
xerror_handler: X failed, continuing
SteamUpdateUI: An X Error occurred
X Error of failed request: BadRequest (invalid request code or no such operation)
Major opcode of failed request: 136 (GLX)
Minor opcode of failed request: 14 (X_GLXGetVisualConfigs)
Serial number of failed request: 51
xerror_handler: X failed, continuing
Looks like steam didn't shutdown cleanly, scheduling immediate update check
Installing breakpad exception handler for appid(Steam)/version(1360621458_client)
Installing breakpad exception handler for appid(Steam)/version(1360621458_client)
Error opening file for reading: Permission denied
unlinked 0 orphaned pipes
removing stale semaphore last operated on by process 3054 with name 0emSteamEngineInstance
removing stale semaphore last operated on by process 3054 with name 0eSteamEngineLock

(process:3150): Gtk-WARNING **: This process is currently running setuid or setgid.
This is not a supported use of GTK+. You must create a helper
program instead. For further details, see:

http://www.gtk.org/setuid.html

Refusing to initialize GTK+.
CAsyncIOManager: 0 threads terminating. 0 reads, 0 writes, 0 deferrals.
CAsyncIOManager: 242 single object sleeps, 0 multi object sleeps
CAsyncIOManager: 0 single object alertable sleeps, 1 multi object alertable sleeps
framefunction.cpp (120) : Assertion Failed: CFrameFunctionMgr::~CFrameFunctionMgr: non static FrameFunction still registered
Assert( Assertion Failed: CFrameFunctionMgr::~CFrameFunctionMgr: non static FrameFunction still registered ):/home/buildbot/buildslave_steam/steam_rel_client_ubuntu12_linux/build/src/common/framefunction.cpp:120

Installing breakpad exception handler for appid(Steam)/version(1360621458_client)
peek of pipe from 0/0 failed: 11

It hangs after the last line, only quitting with ctrl+c

Update: After a reinstall of Steam, it no longer hangs but I get this:
Fatal Error: Steam failed to load: *SteamStartEngine(0xfff0b2b0) failed with error 1: Failed to create pipe: 13

Update 2: I'm able to run the game using this crude workaround: http://steamcommunity.com/app/221410/discussions/0/846938351012409765/
Alas, the anti-aliasing problem still exists, as does middle-click artefacts. Here is a screen of loading anti-aliasing for the first time:
http://s9.postimage.org/3mgj18n67/TF2_Artefacts.png
Here is a screen with the in-game fps, and the absense of the rgba decode with poor performance:
http://s12.postimage.org/819eht9kd/TF2_No_Color_Decode.png