One of the Information Privacy Principles under the Act (and this is coming from a real lawyer) is that you're entitled to access and correct personal information held about you. 2Degrees cannot possibly have referred you to the debt collectors without holding some proof of debt. For that matter, if someone says you owe them money, common law and basic decency requires that they show some proof of debt.
I'd encourage you to not just let the 2Degrees complaints people handle this. Take it to the Telecommunications Disputes Resolution services if you are in any way still dissatisfied and go to the media if need be. Stuffing up someone's credit file when they appear to have done nothing wrong is totally unacceptable. Seeing this and other examples that Mauricio has linked to confirms my previous view that 2D is to be avoided at all costs.
2Degrees: if what the OP is asserting is true, you really might want to start becoming a bit more compliant with the laws of the land. Oh and I guess fixing up ongoing issues like this in good time would help too.