Blender Cycles 2.69 on Ubuntu Server 13.10 64bit
I figured out a way to get it to work:
Instead of using the launchpad version I downloaded the GNU/Linux version from Blender site. Using this version Cycles works fine.