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...)
It is mentioned in the [release notes|http://download.oracle.com/docs/cd/B19306_01/relnotes.102/b15659/toc.htm#CJAFABGC] for 10gR2 on rhel 5.
More insight to this problem gives the Note 454196.1
Btw (just if you not seen it yet) , your question on cx_oracle mailing list was resolved - i've seen today cx_oracle 5.0.2 is released with the resolution for your problem.