I installed empathy, telepathy-gabble, telepathy-stream-engine, and gstreamer0.10-ffmpeg, all from Debian Sid. At this point the calls were always failing, they went through the state "Ringing" directly to "Closed".
Finally I installed gstreamer0.10-ffmpeg-full from debian-multimedia.org and the calls are now working. I provide logs from the failing connections as it could be of interest for you.
Created attachment 16149 [details]
Full gabble log
Created attachment 16150 [details]
Full stream engine log
Created attachment 16151 [details]
Gabble log from the start of the call
Created attachment 16152 [details]
Stream engine log from the start of the call