Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

We consent to the incorporation by reference in this Form 8-K/A, of our report dated March 12, 2004, with respect to the consolidated financial statements and schedule of Metrocall Holdings, Inc. included in its annual report on Form 10-K for the year ended December 31, 2003, filed with the Securities and Exchange Commission.

/s/ Ernst & Young LLP  

McLean, Virginia
November 17, 2004