Update: I can now provide more information on this issue. I had a buddy come over with a windows machine. He had iTunes already installed, so i didn't even have to install it :). So to get on with it:

I connected my Ipod to his PC. Itunes recognized it and opened automaticaly, rewriting my database, I assume. I then ejected the Ipod, and it did no longer contain double entries. I then connected my Ipod to my ubuntu machine, deleted "Apocalyptica" and re-uploaded the songs. My Ipod then again contained a double entry on the Artist "Apocalyptica" (contrary to my first post it does seem to appear on certain artists only!). So I re-connected my ipod to my buddys windows machine again, and just as I expected, it removed the double entry from my database. I then used the opportunity to update my ipod to 1.2.3 (latest firmware according to iTunes), and retried the steps described above. Unfortunatelly, the problem still exists, even with latest apple ipod Firmware.

So I assume it's an issue with gtkpod/libgpod, correct? If it is, what else can I provide you with to find the bug? I have no coding knowledge unfortunatelly, but I am willing to do what you say :)