Labour leader David Shearer says John Key's story about what, and when, he knew about illegal spying on Kim Dotcom is "unravelling".
A review of Government Communications Security Bureau (GCSB) files has revealed Key was told about the spy agency's role in the Kim Dotcom case in February.
Until now, Key has insisted he wasn't told until September 17 - when he was briefed about illegal snooping by the agency. He can't remember the reference in February, but accepts it took place.
"This isn't a case of 'brain fade'. It points to the prime minister not telling the truth. His credibility and integrity, and the entire intelligence network that he heads, are seriously in question,'' Shearer said.
Labour has called for a full inquiry and Shearer said new revelations about other instances of illegal spying added weight to the call.
''There must be an investigation from the bottom to the very top, including the role of the person in charge - John Key. That investigation should include what he knew, what he was told and what he should have known.''
Green party co-leader Russel Norman said Key has either misled the public ''or isn't doing his job as the minister in charge''.
"It's his duty and his job, as spelled out in law, to control the functions of the bureau. His hands-off approach also apparently extends to not paying attention when he is told important information,'' he said.
He added: "If John Key is finding the job of controlling the GCSB a bit hard maybe he should appoint another minister.''
Three more cases of possible illegal spying have also been identified.
Key visited GCSB offices on February 29 for a briefing and to meet staff. A presentation contained a short reference to the Dotcom arrest in January ''as an example of cooperation between the GCSB and the police.''
''The presentation was an electronic slide presentation. The cover slide was a montage of 11 small images, one of which was of Mr Dotcom,'' Key said.
No written record was kept of the meeting and he wasn't given a copy of the briefing.
Key says no reference was made to questions about residency status.
However, it has been revealed that on February 16 police told GCSB that the spying may have been illegal - but GCSB's legal department concluded there was no problem.
The review was conducted by director Ian Fletcher.
In three - out of 58 cases - the GCSB cannot ''assure me that the legal position is totally clear,'' Key said.
''More legal work is being undertaken and the GCSB will issue a further public statement when that work has been concluded."
Fletcher had admitted that in 2009 police asked GCSB for call data records for a New Zealand citizen's telephone.
No surveillance was carried out - but they did tell police the phone was active.
''The GCSB is looking further into the legal aspects of this case.''
Two further cases are being ''clarified''. Both cases involved police warrants and GCSB provided technical data.
The Inspector General will further examine the cases.
Key said he will correct his answers to Parliament on October 16.
Fletcher alerted him to the briefing on Tuesday - just over two weeks after they first told him of the illegal spying blunder. He had asked Fletcher for an assurance the Bureau had reviewed all their Dotcom related files.
A further review was done and GCSB gave Key the details last night.
"I have been clear from the outset that I received no briefing on the operation from GCSB prior to 17 September, and this review confirms that," Key said.
"While neither the GCSB Director nor I can recall the reference to the Dotcom matter being made during my visit to the bureau back in February, I accept that it may well have been made.''