I think I've got this figured out, but I wanted to post it in hopes that future websarchers will find it.
I installed Oracle XE (10.1) and cx_Oracle (5.0.1) on a new Fedora 10 machine, attempted to import cx_Oracle, and got
ImportError: /usr/lib/oracle/xe/app/oracle/product/10.2.0/server/lib/libclntsh.so.10.1: cannot restore segment prot after reloc: Permission denied
I fixed this by disabling SELinux (enabled by default on Fedora), as described at http://www.crypt.gen.nz/selinux/disable_selinux.html - the short version is "echo 0 > /selinux/enforce"
Because libclntsh.so.10.1 is at the heart of the error, I assume the problem is not really from cx_Oracle, but from Oracle itself - and Oracle never promised to support SELinux, so far as I know. So perhaps it simply must be accepted as an incompatibility. (Still, everybody who sees the irony of Oracle being incompatible with an important Linux security measure, raise your hand...)