Balchy: As said, this discussion is not about the debt it is about their right to cancel accounts without proper investigation or authorisation, same with transferring funds from one account to a totally separate account.
The debt side of things is an ancillary issue and not entirely relevant to the discussion
Trade Me, in my view, have taken very reasonably steps here given the information you have told us.
I would suspect in this case the issue has been exagerated by the fact you and your wife share a birthday, albeit a year apart.
Trade Me would be looking at a number of factors, and this is one piece of the puzzle, which combined with the other things you mention (Same Credit Card, surname, address etc) have let them to believe you and your wife are one in the same (Which, in some ways may be true).
Changing the year of birth is a common way for people to avoid paying debt, and in your case it is an unfortunate coincidence.
However like I said, if you pay the debt i'm sure they will be happy to restore both accounts.
Like I said earlier, you would never be in this situation if you did not breach their Terms and Conditions by not immedaitely paying your debt.
Pay what you owe, and be thankful all that happened was a suspended account, and not a black mark against your credit rating.