I tried to cancel a gym membership over the phone and was told by the girl it would be taken care of. Then I end up in collections for not paying dues. The gym is telling me it’s illegal to cancel a membership over the phone. Is this so? Also they won’t provide me a copy of my contract.
It is not illegal per se to cancel a contract over the phone, or by any other means of communication. The contract itself might, however, require that a cancellation be done in writing, must be hand-delivered, or whatever it says. You would have to look at the contract to see what the conditions for cancellation are.
When you first enter into a contract, you have an opportunity to get a copy of the contract, for example you walk into the facility and sign an agreement, and you should then be given a copy. But it is possible that they will fail to give you a copy, or they might even refuse to give you a copy. It is possible that, as a consumer, the law of your state requires businesses to give copies of contracts to customers. If not, then this is the situation where you had a choice to agree to their offer only if you get a copy. If they intend to take you to court for breach of contract, they will have to provide a copy in order to prove to the court that you have violated the terms.
Even if the contract says that contract cancellations must be by certified mail delivered to Nepal, the company will be held responsible for the representations of their authorized agents. They might try to introduce the contract into the dispute, but you can prevent them from doing that, using "promissory estoppel", because in effect you relied on their promise to cancel the contract. Their best hope is to dispute your claim that their agent made such a promise.
In line with user6726's answer, the real problem is that the gym is likely to deny that its employee accepted your notice of cancellation over the phone.
If you haven't done so, request in writing (by email or having the gym sign a receipt of your request) a copy of the contract. Evidence of the gym's (I wold say unreasonable) refusals to provide you with a copy tends to prove that the gym is departing from the implied covenant of good faith and fair dealing that is expected in contract law.
To illustrate the potential relevance of the gym's refusal, see Resource Management Co., v. Weston Ranch, 706 P.2d 1028, 1048 (1985):
One additional finding, pertaining to the Westons' understanding of the contractual terms that should be addressed, is the trial court's finding that Stevenson refused after the September 20 meeting to give a copy of the contract to George Weston for examination and that as a consequence none of the Westons had a full understanding of the contract's terms. [...] There is no evidence in the record indicating that George Weston asked for a copy of the contract following the principal September 20 meeting, much less any evidence indicating that Stevenson refused such a request.