SNOM Phones intermittent after Trixbox Local to FPB Hosted

I had a local Trixbox installation that worked fine for several years, I am moving to a hosted freepbx Distro 2.10.1.9.
We are up an running but several of my SMON 300 and 360 (version 8 s/w) phones seem to be losing their connections; Switching to non-registered. A look at the phone log shows as below.

Anyone seen this before? Ideas on where to look?
(IP Address has been ###'ed out and domain name changed for security)

6/8/2013 12:29:18 [ERROR ] PHN: SIP: Registrar [email protected] timed out
16/8/2013 12:33:42 [CRITIC] PHN: SIP: packet 1000035 dest invalid udp:###.###.###.###:5060 for Request DISCOVER/-
16/8/2013 12:34:14 [ERROR ] PHN: SIP: transaction_timeout udp: 1000034 (32000)
16/8/2013 12:34:14 [ERROR ] PHN: SIP: transport error: 1000034 -> udp:###.###.###.###:5060
16/8/2013 12:34:14 [NOTICE] PHN: SIP: Add dirty host: udp:###.###.###.###:5060 (0 sec)
16/8/2013 12:34:14 [NOTICE] PHN: SIP: final transport error: 1000034 -> udp:###.###.###.###:5060
16/8/2013 12:34:14 [ERROR ] PHN: SIP: transport error 1000034: generating fake 599
16/8/2013 12:34:14 [ERROR ] PHN: SIP: Registrar [email protected] timed out
16/8/2013 12:35:16 [NOTICE] PHN: TPL: Socket 25 idle/connect timeout

Setup a VPN tunnel to your hosting provider. Your NAT is not working consistently.

this smells like a firewall/router issue to me.