Supay, I just reinstalled (the game had been crashing frequently since Charlemagne) and am having the same issue. I'm going to try your solution; thank goodness this thread is still around.
Just a note, these case-random files are just the result of Paradox not being used to programming for case-sensitive filesystems; NTFS, FAT, etc (the MS fs's) are, by default, case-insensitive. So everything works fine in Windows, but breaks like crazy on Linux, because sometimes their code says "Bow_02.xac" and other times "bow_02.xac". Since you already have Steam in a subvolume, you might be able to disable case-sensitivity in the fs for just your Steam subvol to avoid errors in the future.
This should be a good heads-up to Paradox to ALWAYS program case-sensitively, just to be careful. Case-sensitive fs's aren't just a Linux thing; I'm pretty sure it can be enabled on Windows's fs's, and I think Mac (derived from BSD, a UNIX-like (UNIX and BSD fs's were/are case-sensitive) fs's come case-sensitive, too.
EDIT: hot-damn, it worked!

I made sure to symlink the renamed files to their original names, just in case. Thanks for posting your solution here.

EDIT: mah, the re-install didn't fix the frequent crashing. :\
EDIT: found a suggestion to try adding "-threads=1" to the commandline; I guess multithreading's a bit buggy on Linux, too. Going to give it a go and see if it fixes the crashing. EDIT: apparently, the multithreading issues have already been fixed.
EDIT: didn't fix the crashing. :\
EDIT: I'm quite certain the problem is due to sloppy, case-insensitive coding, so, if anyone else, on Arch or whatever, is having random problems with CK2 et al and not with other games, try putting your SteamApps/common folder onto a case-insensitive fs, like ntfs. I'm going to give this a go now; it would likely have avoided nearly all of the issues we've experienced. I'll report back if it works.
EDIT: I've moved the files to an NTFS partition, and mounted the partition with with the
ignore-case parameter (this ignores case on
reads, but not
writes, so, to be safe, you should also use the
windows_names parameter, which disables case-sensitivity only for
writes)) with
lowntfs-3g (you have to use lowntfs-3g; ignore-case won't work with normal ntfs-3g). I'm still getting a crash, and with the same error: "terminate called after throwing an instance of 'CFileException'". Going to try validating files; maybe something weird happened during the move.
EDIT: Nope, everything validated. Going to try reinstalling again.
EDIT: Aaand I'm back at square one: broken DLC again. This means that, for whatever reason, case-sensitive reads are still being performed on the partition.
EDIT: Apparently, lowntfs-3g and ignore-case aren't working right; it says
here that when these are used in tandem, all files should be shown as lowercase, but they're still mixed-case for me.
EDIT: I'm typing "sudo lowntfs-3g -o defaults,users,windows_names,ignore-case -v /dev/sdb2 /media/WIN7". This is the correct syntax; I have no idea why it wouldn't be displaying everything in lowercase.
If anyone feels up to it, you might be able to effectively disable case-sensitivity on a Linux fs just by creating a bash script that lowercases everything (done, see below), or, more complicatedly, that makes lowercase symlinks to mixed-case filenames (done, see below; and was actually less complicated the the formest), or, even more complicatedly, that makes a symlink for every file for every possible case variation (I'm not going to try script this, because it would be a giant pain and extremely inelegant). I remember that I had some trouble with symlinks and ck2 earlier, though. I'm going to see if I can write the first proposed script, since that should be pretty simple (famous last words).
EDIT: Alright, I've got something that works, but only in a single directory; so, you need to run it manually in every directory. I'm working out the recursive part. Here it is:
http://pastebin.com/CH0LyQcU
EDIT: This *should* work; I'm going to try it out right now:
http://pastebin.com/JxFJAdnM
EDIT: Fixed several bugs from the last version, but still doesn't work in the ck2 dir:
http://pastebin.com/jAc5L198
EDIT: Cleaned it up some; functionally identical to the last version:
http://pastebin.com/EPh8g5pB
EDIT: Likely the last version I'll post before going to bed (it's 5AM

).
http://pastebin.com/5xhKE7SZ
EDIT: Okay, so, I've got it working in the current directory and the alphabetically first subdirectory:
http://pastebin.com/VY1FGMhU
EDIT: Okay, got it to recurse through all subfolders!

Unfortunately, the decapitalization part seems to be broken again. Here's the latest version:
http://pastebin.com/rsDAj7z5
EDIT: I got it working!

Well, at the cost of unicode support. PasteBin is mad at me for making so many pastes, so I'll just keep the most current version of the file here.