I saw your post, in my (long) quest for the solution to my molekel issues, and now that got it right I returned to try to help you out. I used to get this error:
/home/agapito/opt/molekel/bin/molekel4.3.linux: relocation error: /home/agapito/opt/molekel/bin/molekel4.3.linux: undefined symbol: __builtin_new
This was due to libstdc++ issues, as I found out latter. All I did was install all the libstdc++ available for my distro (Ubuntu Hoary) and then tried to make the link that molekel needs to each one of them, one at a time. I found out that the package I had to install was called libstdc++2.10-glibc2.2. That installed libstdc++-3-libc6.2-2-2.10.0.so wich enabled me to run molekel.
Hope that works for you.
By the way, I think you'll be happy to know that the molekel project is back, and that it's going to be Open Source.
The alpha version is still very primitive and lacks a lot of features, but it looks nice.
Check it out here:
http://www.cscs.ch/a-display.php?id=138