Thanks. Somehow people need to keep reminding me of that tool.
I've found a different cause/solution, and it's quite weird. I recently upgraded FreeNX, and this could be causing it.
The command
reveals openoffice is looking for libXcomp.so at various places, it it'll find it in /usr/NX/lib/ at my system.
Removing /usr/NX/lib/ from /etc/ld.so.conf and running
ldconfig again solved my problem, OpenOffice no longer found libXcomp.so and didn't get the symbol clash.
I'm still confused who's fault this is though.. (OpenOffice, NX, my FreeNX upgrade or my gcc-3.4 upgrade) And I've likely broken FreeNX now.