Almost identical to my problems, a couple of days ago my employer issued me with a Bold 9700, Orange network is non existent at home and therefore the UMA facility is essential.
My ISP is BT and I have two broadband lines into my home, one with a new Homehub router and one with a Netgear DG834.
I too have been through all the usual: turn off, take battery out, switch modem off and on, WI-Fi only/ WI-Fi preferred, Wireless G only, etc.
The hand set will sometimes get a UMA connection, seems to be completely random though and can take hours to establish this connection, the results with Netgear and BT Homehub routers are the same.
A senior techie guy at Orange, recommended Port Forwarding or purchasing a Linksys router which he preferred and/or the following:-
If UMA is not being used on an Orange Broadband/Livebox Configuration, then the following settings may help.
Firewall port numbers and URL
xxx8226; UMA uses standard IPSec ports 500 & 4500 for IKE
xxx8226; Ports 50 and 51 are used for ESP and AH
xxx8226; unc.singlephone.orange.co.uk (advised) or 193.35.136.240 /28
I certainly wouldn't have a clue what the above port malarkey is all about.
This is driving me crazy.