Disclaimer: I don't know a huge amount about cellular networks, so take this with a grain of salt...
Could it be something to do with the device roaming to VF because it can't connect to 2D? I see that it doesn't support 2100MHz - could it be that local 2D in your area is 2100MHz only, so it's connecting to VF 900MHz instead?
Just to close off this topic... 2 Degrees have been in contact and done a good level of troubleshooting. There is a compatibility issue between my new GPS tracker and 2 Degrees network and they are unable to make it work. Further investigation has uncovered several others with similar (not always identical) units that have the same issue with 2 Degrees in NZ. The only workable solution has been to replace the SIM with a VF prepay SIM.
I should point out that 2D have been helpful and professional through the whole process and in no way would I expect them to support a cheapo Chinese GPS tracker which is very hard to troubleshoot (no interface or configuration options without SMS working!)
I got a VF SIM and the unit started responding just fine.