I had been a customer of Telecom's Xtra broadband for a long period of time with no issues until the roll out of thier Faster, Cheaper internet. My internet speed disappeared overnight, I battled with Xtra's Helpdesk for 2 months, constantly hearing the same thing. You're to far from the exchange to get a fast connection, the best you can expect is 400K. Prior to the rollout I was getting 1.2Mbs.
Onto the solution,
I took a gamble and moved all services to Slingshot. Wow, it fixed the internet issue.
Connection speeds are between 800K and 1.2Mbs. I would say this shows the rubbish that Xtra's helpdesk was fobbing me off with.
I would recommend giving another internet provider a shot, you have nothing to loose. Xtra has.
By the way, the change over was nearly painless. Xtra stuffed up by dropping my connection several days before the date they should have. Go figure. Slingshot were excellent and friendly. There helpdesk is knowledgable too. Highly recommended.