Well, a month has passed... After reinstalling the whole desktop (just because I wanted to have a clean start after the summerbreak) I thought of taking up the Ekiga-problem again.
I just couldn't believe that my modem/router would give all the problems, so I started all over again.
And guess what? I found a solution!
The whole thing had to do with a bad connection with the stun-server. That caused the error message.
To solve it, open gconf-editor and click the tickbox in apps->ekiga->general->nat->disable-stun.
Sound, playback and video are all working.