How do I save purchased apps as APKs? I am unable to save APK's that I have purchased (actually paid for) through the Play store. Usually SaveAPK is able to save the APKs that I'm interested it, however this didn't work: it sais Copy failed. I also tried Astro File Manager, but every app that I purchased had a lock symbol on it, and it didn't allow me to back it up.

Next, I tried looking in /data/app, and I couldn't find the APK either. Any ideas where they could be? Maybe it's some sort of copy protection in 4.x+ which I haven't heard of previously.

I am running Cyanogenmod 10.1-20130714-NIGHTLY-i9300
Yes, this is a new feature (app encryption with forward locking) introduced in Android 4.1 (Jelly Bean) which is intended to prevent casual copying of .apk files. See this blog post for a more detailed description of this feature, with some technical details.

Part of the post text which is most relevant to this question:


  A typical forward locked app's mount point now looks like this:

shell@android:/mnt/asec/org.mypackage-1 # ls -l
ls -l
drwxr-xr-x system   system            2012-07-16 15:07 lib
drwx------ root     root              1970-01-01 09:00 lost+found
-rw-r----- system   u0_a96    1319057 2012-07-16 15:07 pkg.apk
-rw-r--r-- system   system     526091 2012-07-16 15:07 res.zip

  
  Here the res.zip holds app resources and is world-readable, while
  the pkg.apk file which hold the full APK is only readable by the
  system and the app's dedicated user (u0_a96).


So a normal app like SaveAPK cannot read .apk files of forward locked apps in JB (but app resources are still world-readable, therefore apps which contain icon sets and themes for other apps will still work properly).

However, this protection is effective only in the locked-down state of Android as shipped by device manufacturers. If you have root, you can still access .apk files of all applications installed on your device and do whatever you want with them. The only problem for you is that some backup apps you have used previously will no longer work, and you need to find a working replacement (now a backup app will need to use root access in order to backup all .apk files).