Basically I open the Marketplace on the handset itself, hit the [INSTALL] or [UPDATE] button and after a bit of thinking the device shows me this message:

"The Windows Live ID service is unavailable at the moment. Try again later".
This doesn't happen if I am using WiFi at home for example (where the ISP is TelstraClear). I am using the internet.telecom.co.nz APN.
If I use WiFi at home and install and app, I can turn WiFi off and continue installing apps over Telecom XT. If I restart the handset the the Marketplace stops working over Telecom XT.
This makes me think it could be some DNS problem on Telecom XT.
Anyone else seeing this happening?