I'm running the game on Ubuntu 14.04 with a GeForce GTX 570 without any issues. Could you try to describe the issue in more detail? Does the issue appear at the main menu, or does it appear once you launch a game?
I would suggest to do a complete re-install of the game. To make sure there isn't anything wrong with the actual files or anything. Remember to also delete the Crusader Kings II folder at "/home/USERNAME/.paradoxinteractive/Crusader Kings II". This is where the game stores all save games, logs etc. BUT REMEMBER TO BACKUP any save game you want to keep before your delete everything!
I would suggest to do a complete re-install of the game. To make sure there isn't anything wrong with the actual files or anything. Remember to also delete the Crusader Kings II folder at "/home/USERNAME/.paradoxinteractive/Crusader Kings II". This is where the game stores all save games, logs etc. BUT REMEMBER TO BACKUP any save game you want to keep before your delete everything!