I finally got my phone back from Telstra for a warranty claim. For those who don't pay attention to obscure threads on developer forums, don't plug an external antenna into a GSM Galaxy Nexus. Apparently it's a not-uncommon (but not 100%) problem where you plug an external antenna in (I only did once, as a test) and the internal antenna never reconnects. I had 0 bars and only sporadic SMS service inside the Telstra shop, where they have active repeaters to give the illusion that you'll get full-bars of service inside a shopping mall.
I was told to allow 2~3 weeks, but was pleasantly surprised - I think it was only about a 9 day turnaround. They didn't charge me for it apparently, which was a relief because the first girl I spoke to at the Telstra shop seemed to imply that "everyone knows" you don't plug external antennas into Android phones and that I'd voided the warranty. I'll be getting a passive radiator pad for it rather than re-using the socket, but I still don't think it's my fault.
It may be a "factory test" socket, but if it looks like an external antenna socket and functions like an external antenna socket, and I didn't have to remove any "warranty void if removed" stickers then there's no reason I shouldn't be allowed to use it. I won't in future, but at least now I'm aware of the problems.
I'm just glad to have it back (a Motorola Defy just wasn't cutting it) and glad it doesn't appear to have cost me anything but a few days without my phone. Oh and they cleared the data, but I was expecting that.