"We had a problem with the maintenance... (the airline) not being able to give us certain information pertaining to the airworthiness of the aircraft," said CAA aircraft safety executive manager Obert Chakarisa.
However, Nationwide said it was still waiting for CAA notification on its request to recommence its international service between Johannesburg and London-Gatwick.
"In order not to create further confusion or inconvenience, Nationwide has no option but to cancel tonight's flight," it said in a statement.
"We apologise for the further disruption that this has caused."
The Nationwide flight was to have departed Johannesburg at 21:05.
Still outstanding issues
Chakarisa, meanwhile, said the airline had been notified of the issues "still outstanding". These pertained only to the airline's Boeing 767.
Nationwide was grounded on Friday after the CAA suspended its approval of the airline's aircraft maintenance organisation (AMO) and suspended the certificates of airworthiness of Nationwide's fleet of aircraft, including the Boeing 767.
Nationwide has lodged an appeal against the decision with the acting Commissioner of Civil Aviation, Gawie Bestbier.
He said on Sunday that the CAA had yet to present the case to him for assessment.
Documentation inspected
CAA inspectors spent most of Sunday examining the Boeing 767 Nationwide intended using on the flight, and inspecting its documentation, said Chakarisa, adding that he participated in the inspection.
"I saw first hand what was happening... I was able to see the difficulties they experienced trying to pull out the information we were requiring," he said.
This was "very basic information every airline has to be able to provide very easily". "The airworthiness condition of aircraft is based on this information," he said.
"They didn't even have the basics."
Chakarisa said paperwork was a critical component of the administration of any airline.
Certain aircraft parts were life-limited and had to be removed, or overhauled, or serviced at certain intervals.
If an airline was unable to tell what the life of a part was the chances of it over-running that life were high and the risk of an accident was therefore high.
Life status of components
He said Nationwide was, among other things, unable to indicate the life status of components on the leased Boeing 767.
The airline was the custodian of its maintenance and service records even though the Dutch airline KLM was responsible for its major maintenance.
The CAA could not take the risk of allowing the aircraft's continued operation until this was possible.
"They are serious safety issues."
The CAA was picking up a "systematic breakdown" at Nationwide, said Chakarisa.
He said allowances had been made regarding the airline's appointment of new staff, but it was still "not operating to the level we expect".
Supplied CAA with full history
Nationwide said it had supplied the CAA with the aircraft's full operational and service history on Sunday.
This included the complete paper trail dating back to its manufacture and its history under its previous owners, Aeromexico and Air Canada.
"This information was supplied to the CAA today (on Sunday), as it was in 2003, when the CAA inspected the aircraft in Montreal prior to its import to South Africa," said the airline.
Clean bill of health
"At that time, the CAA gave the aircraft a clean bill of health under its process for placing the aircraft on the SA civil aircraft register."
Its placement on the register was the equivalent of the CAA giving it "a clean bill of health", Nationwide said.
Nationwide said it continued to work around the clock to resolve the crisis, demonstrate its fitness and restore its normal services.
The airline hoped to be fully operational within a week.