すみません。自己解決です。

ネット上を長い間探していたら、過去に2ちゃんねるにて同じような状況になった人がいたことがわかりました。
それによると、AMDのCatalystドライバーを入れたあとにカーネルをアップデートするのがいけないということだそうです。解決方法はATIバイナリX.orgドライバー（たぶんfglrx）というものを入れることです。誰かが同じ状況に遭っていると思うので、https://wiki.ubuntulinux.jp/UbuntuTips/Hardware/RadeonErrorを作成しておきました。