Eu tenho o mesmo problema e ainda não o resolvi. Mas eu descobri o que há de errado.
Gostaria de receber alguns conselhos de especialistas, mas parece que o FGLRX NÃO funciona no Ubuntu 16.04 e no mais recente 14.04 (5) porque não é compatível com uma versão recente do XORG.
Aqui está uma explicação:
Ubuntu 14.04.5 / 16.04 / 16.10 e gráficos da AMD
Please Note: 14.04.5 brought with it Xorg 1.18, which is what causes the problem in 16.04 to begin with. Luckily, it is completely possible to downgrade Xorg to 1.16 (on 14.04), so you can still use fglrx. Read here.
Na verdade, eu precisava do APK da AMD para codificar no OpenCL 2.0, então acho que tenho apenas que evitar os drivers da AMD e encontrar outra maneira de instalar o OpenCL.
Uma solução sugerida na página vinculada é:
Try out Oibaf's drivers.
They work for AMD, NVIDIA and Intel, so you can even try them out if you dislike NVIDIA's proprietary drivers or are hoping for more performance from your Intel card.
They support newer OpenGL and OpenCL versions, so stuff that depends on those will work.
They claim to be optimized, so you could see an real boost in performance.
O driver do Oibaf parece ser um ótimo substituto para o fglrx, e provavelmente é. No entanto, se você tiver uma placa AMD realmente recente, poderá experimentar a própria oferta da AMD.