I've run into some Android phones that just don't work well with VOIP. I tried and tried on several US Verizon Androids and didn't succeed even though I configured the same model on other networks. I was suspicious that the carrier had done something.

If you are having problems and your phone isn't Vanilla, I might suggest rooting it and reflashing it with a generic version of the OS.