Thank you, so you suggest that the real problem can be different and related to the driver/card. What about install another distro (maybe Ubuntu 16.04) in another partition and share the home for this test? Anyone can see particular problem with steam?
I think the same about the driver, r600.

I'm on Ubuntu 14.04, I left Gentoo maybe a couple of year ago.

Just a small update, after moving to 16.04 so open driver and deleting the .steam folder (except the userdata and steamapps forlders) the game now starts. It is impossible to play also on all minimum/off, the benchmark returns min 1.4 avg 8.4 max 11.4. A little strange is that also the initial video is lagging.

I saw on another post that you installed the Oibaf PPA.
You can install a Gallium Nine patched Wine and try the game with it.
This can be a solution while waiting the open-source drivers to mature a bit more

You will miss some Linux and Dx11 specific graphical settings but I guess you won't need them anyway :)

Thank you, for this game it was just a test, my hardware is not good enough. As said, I was just curious because I was able to play Bioschock Infinite without problem.
I can wait to play it, I'm thinking to buy a new pc hoping to resist until zen/vega but it is hard...