Update: The AP has written this letter to DOJ. It includes this paragraph:

While we evaluate our options we urgently request that you immediately return to the AP the telephone toll records that the Department subpoenaed and destroy all copies. (my emphasis)

Here are DOJ's guidelines for obtaining records from reporters.

The policies, procedures and standards governing the issuance of subpoenas to members of the news media, subpoenas for the telephone toll records of members of the news media, and the interrogation, indictment, or arrest of members of the news media are set forth in 28 C.F.R. § 50.10.

From 28 CFR 50.10(g):

(g) In requesting the Attorney General’s authorization for a subpoena for the telephone toll records of members of the news media, the following principles will apply:

(1) There should be reasonable ground to believe that a crime has been committed and that the information sought is essential to the successful investigation of that crime. The subpoena should be as narrowly drawn as possible; it should be directed at relevant information regarding a limited subject matter and should cover a reasonably limited time period. In addition, prior to seeking the Attorney General’s authorization, the government should have pursued all reasonable alternative investigation steps as required by paragraph (b) of this section.

(2) When there have been negotiations with a member of the news media whose telephone toll records are to be subpoenaed, the member shall be given reasonable and timely notice of the determination of the Attorney General to authorize the subpoena and that the government intends to issue it.

(3) When the telephone toll records of a member of the news media have been subpoenaed without the notice provided for in paragraph (e)(2) of this section, notification of the subpoena shall be given the member of the news media as soon thereafter as it is determined that such notification will no longer pose a clear and substantial threat to the integrity of the investigation. In any event, such notification shall occur within 45 days of any return made pursuant to the subpoena, except that the responsible Assistant Attorney General may authorize delay of notification for no more than an additional 45 days. (my emphasis)

The AP's objections include:

That the Department undertook this unprecedented step without providing any notice to the AP, and without taking any steps to narrow the scope of its subpoenas to matters actually relevant to an ongoing investigation, is particularly troubling.

While the telephone toll records covered a two month period in May, 2012, it's not clear when they were obtained. The AP writes:

Last Friday afternoon, AP General Counsel Laura Malone received a letter from the office of United States Attorney Ronald C. Machen Jr. advising that, at some unidentified time earlier this year, the Department obtained telephone toll records for more than 20 separate telephone lines assigned to the AP and its journalists. The records that were secretly obtained cover a full two-month period in early 2012 and, at least as described in Mr. Machen’s letter, include all such records for, among other phone lines, an AP general phone number in New York City as well as AP bureaus in New York City, Washington, D.C., Hartford, Connecticut, and at the House of Representatives.

This action was taken without advance notice to AP or to any of the affected journalists, and even after the fact no notice has been sent to individual journalists whose home phones and cell phone records were seized by the Department.

If the phone records were obtained "earlier this year" and the DOJ has 45 days, plus the option of a 45 day extension to give notice, the notice may have been timely.

I think the greater problem in the overbreadth of the records sought and obtained and DOJ's failure to narrowly tailor its records request to the perceived need for them:

The Department obtained telephone toll records for more than 20 separate telephone lines assigned to the AP and its journalists. The records that were secretly obtained cover a full two-month period in early 2012 and, at least as described in Mr. Machen’s letter, include all such records for, among other phone lines, an AP general phone number in New York City as well as AP bureaus in New York City, Washington, D.C., Hartford, Connecticut, and at the House of Representatives. This action was taken without advance notice to AP or to any of the affected journalists, and even after the fact no notice has been sent to individual journalists whose home phones and cell phone records were seized by the Department.