Just to add on this thread, I had also "no network" problem on my Phaeton 2009MY with RNS 810 radio and UHV Premium.
And the phones are galaxy s4 and galaxy s6 edge with Three (SE) operator in Sweden.
The car and the phone will nicely connect to each other over the BT, call lists and contacts transferring over, but no network.
Then, I switched over to Comviq (another operator) and new sim card, but my hopes were not that high, as I could never imagine that it would be operator specific problems.
But, now after the initial connection and pairing, my galaxy s6 with Comviq sim card is working flawlessly and with full strength on the network signal and of course there is no limits for my happiness...!
So I can only conclude that the Three was not working with UHV Premium either here in Sweden !