Quoting a source within Verizon, the cable news network said the fired workers were hired to help customers and weren't authorized to access records, unless asked by customers. The Verizon source did not say how many employees were fired.
"We now consider this matter closed," the source told CNN.
A Verizon spokesman on Monday said the company was aware of the report and "wouldn't disagree with it, but we're not confirming nor denying."
The fired employees had only limited access to customers' records, and would not have been able to read text messages or listen to voice mail, CNN reported over the weekend. An Obama spokesman had said that the president-elect no longer used the mobile phone and it had been inactive for months.
Verizon reported the breach last week. Chief executive Lowell McAdam apologized for the incident and said all employees who accessed the account had been suspended with pay.
CNN also reported that Verizon Wireless had launched a separate internal investigation to determine whether customer information "had in any way been compromised outside our company," McAdam said in an internal e-mail obtained by CNN.
The Verizon breach wasn't the first time records related to Obama had been accessed without authorization. In March, State Department officials issued an apology after three employees of a department contractor had accessed the passport files of then presidential candidates Hillary Clinton, John McCain, and Obama.
Employees breaking workplace rules and even federal law to access celebrity records isn't new. UCLA Medical Center employees, for example, snooped on the medical records of actress Farah Fawcett and singer Britney Spears.