Planeshift requires a newer version of Cal3d than that included with Ubuntu. The workaround I used to feed my PS addiction, was to download the newer libcal3d .deb archive from the Debian project and copy them into my ${PS_DIR}/libs directory ( ${PS_DIR being where you installed PlaneShift), using the following steps:
STEP 1 Download Cal3d v12
From
http://packages.debian.org/unstable/libs/libcal3d12 click the link for your architecture (i386 or amd64) and on the following page select a mirror near you. Create a new local directory and save the file to that directory.
STEP 2 Extract the Debian archive.
From terminal window cd to the directory that you created in Step 1 and use the dpkg(1) command to extract the .deb archive into a new directory.
STEP 3 Install New Library
Copy the new library and it's symbolic link from the directory in Step 2 to ${PS_DIR}/libs.
I have installed PlaneShift in /opt/PlaneShift on a i386.
The follow are the actual commands I typed on my box:
> cd ~/libcaltmp
> dpkg -x libcal3d12_0.11.0-2_i386.deb extracted
> cp extracted/usr/lib/libcal3d.so.12* /opt/PlaneShift/libs
The above steps should allow you run PlaneShift without getting an error about libcal3d not being found.

Note: While you *could* use dpkg to install the new library system wide and risk breaking things, I opted to copy them manually so only PlaneShift is affected.
-X