[ 13612.925] (II) fglrx(0): Shutdown CMMQS
[ 13612.925] (II) fglrx(0): [uki] removed 1 reserved context for kernel
[ 13612.925] (II) fglrx(0): [uki] unmapping 8192 bytes of SAREA 0x7394000 at 0xb78a9000
[ 13612.984] (II) fglrx(0): Interrupt handler Shutdown.
I'd wager it's the videodriver, yes. The X backtrace is pretty useless though, and I'm not familiar with AMD cards and their drivers. Have you tried the proprietary Catalyst? And is fglrx the same as xserver-xorg-video-radeon?
[ 13350.029] 0: /usr/bin/X (xorg_backtrace+0x3b) [0x80ef31b]
[ 13350.029] 1: /usr/bin/X (0x8048000+0x5d00d) [0x80a500d]
[ 13350.029] 2: (vdso) (__kernel_rt_sigreturn+0x0) [0x88d40c]
[ 13350.029] Segmentation fault at address 0x50005
Caught signal 11 (Segmentation fault). Server aborting
That said, you could add the bleeding-edge xorg-edgers ppa (ppa:xorg-edgers/ppa) and upgrade to the fresh versions of X and drivers available from there. But obviously there are no guarantees with regards to stability. Caveat installer. Downgrading back is pretty easy though with the ppa-purge tool.
$ sudo add-apt-repository ppa:xorg-edgers/ppa
$ sudo apt-get update
$ sudo apt-get upgrade