I use a sipgate one account with sipdroid, and it works fine. I didn't look over those directions you posted, but I'll post up my settings to see if helps you.
As a note, I'm using the sipdroid client from the android market, so it only works on wifi. If you want it to work over 3G, you need to install it from the sipdroid website.
I don't go through PBXes, I'm configured to log directly into the sipgate servers.
Settings:
Sip Account Settings:
Authorization Username: (From SIP credentials on Sipgate site)
Password: (From SIP credentials on Sipgate site)
Server or Proxy: sipgate.com
Domain: left empty
Username or Caller ID: left empty
Port: 5060
Protocol: UDP
Call Options:
Use WLAN: Checked
Use 3G: Checked (although this doesn't work, since I'm running the market version)
All the rest of the options I have UNchecked in the Call Options menu
I believe I have everything else set to defaults, and this has always worked for me. The only problem I ever had was when I first got my travel router, and it was somehow blocking SIP. I can't remember what setting I had to change on my travel router to get it working, but it works now. It has worked on every other wifi router I've tried.
Since I use a Sipgate 1 account, with free incoming calls, I use the google voice webpage on my droid to setup calls. Worked great when I was in Japan. Free calls back to the US.
