If the collection is still showing in your credit report, did the debt collector update the balance to $0?
If so, and if the OC is not reporting, then there is no inaccuracy in your credit report, and thus there is no issue under the FCRA or FDCPA for a dispute.
Credit report exclusion of the collection would not remove the assertion by the OC, based on their own records, of a continued debt.
Do you have proof that your prior payment resulted in discharge of the debt?
Your issue is apparently their denial of new services based on assertion of a debt still owed to you.
I would call someone in upper management and ask for review of the asserted indebetness.
