MANAGEMENT CONSULTING AGREEMENT

Exhibit 10.22

MANAGEMENT CONSULTING AGREEMENT

This Management Consulting Agreement (the “Agreement”) is made as of April 13, 2005, by and among Hawaiian Telcom Communications, Inc., a Delaware corporation (the “Company”), and TC Group, L.L.C., a Delaware limited liability company (“Carlyle”).

RECITALS:

WHEREAS, Carlyle, by and through its officers, employees, agents, representatives and affiliates, has expertise in the areas of corporate management, finance, product strategy, investment, acquisitions and other matters relating to the business of the Company; and

WHEREAS, the Company desires to avail itself of the expertise of Carlyle in the aforesaid areas, in which it acknowledges the expertise of Carlyle.

AGREEMENT:

NOW, THEREFORE, in consideration of the foregoing recitals and the covenants and conditions herein set forth, the parties hereto agree as follows:

The Company hereby appoints Carlyle to render the advisory and consulting services described in Section 2 hereof for the term of this Agreement.

(a) During the term of this Agreement, Carlyle shall render to the Company, by and through such of Carlyle’s officers, employees, agents, representatives and affiliates as Carlyle, in its sole discretion, shall designate, in cooperation with the Chief Executive Officer, from time to time, advisory, consulting and other services (the “Oversight Services”) in relation to the operations of the Company, strategic planning, domestic marketing and financial oversight and including, without limitation, advisory and consulting services in relation to the selection, retention and supervision of independent auditors, the selection, retention and supervision of outside legal counsel, the selection, retention and supervision of investment bankers or other financial advisors or consultants and the structuring and implementation of equity participation plans, employee benefit plans and other incentive arrangements for certain key executives of the Company.

(b) The parties hereto acknowledge that certain events will require Carlyle to render services beyond the scope of activities which the parties contemplate as part of the Oversight Services and for which Carlyle shall be entitled to additional compensation hereunder. It is expressly agreed that the Oversight Services shall not include Investment Banking Services. “Investment Banking Services” means investment banking, financial advisory or any other services rendered by Carlyle to the Company in connection with any acquisitions

and divestitures by the Company or any of its subsidiaries, including, without limitation, the sale of substantially all or any portion of the assets of the Company, whether by a sale of assets, the equity interests of the Company, merger or otherwise, and the acquisition or sale of any subsidiary, division or service area of the Company, or the public or private sale of debt or equity interests of the Company, or any of its affiliates or any similar financing transactions. The Oversight Services and the Investment Banking Services shall be referred to herein as the “Services.”

(a) In consideration of the performance of the Oversight Services contemplated by Section 2(a) hereof, the Company agrees to pay to Carlyle (i) a closing fee of $16,000,000 in connection with the transactions contemplated by the Agreement of Merger among GTE Corporation, Verizon HoldCo LLC, Paradise HoldCo, Inc. (n/k/a Hawaiian Telcom HoldCo, Inc.) and the Company, dated as of May 21, 2004, as amended (the “Merger Agreement”) and (ii) an aggregate per annum fee (the “Fee”), continuing until such time as this Agreement is terminated in accordance with Section 6, an amount equal to $1,000,000 per annum. The Fee shall be payable quarterly in advance beginning on the Closing Date (as defined in the Merger Agreement). Fee payments shall be non-refundable.

(b) In consideration of any Investment Banking Services provided to the Company, Carlyle shall be entitled to receive additional reasonable compensation as agreed upon by the parties hereto and approved by a majority of the members of the board of directors of the Company.

In addition to the compensation payable to Carlyle pursuant to Section 3 hereof, the Company shall, at the direction of Carlyle, pay directly, or reimburse Carlyle for, its reasonable Out-of-Pocket Expenses. For the purposes of this Agreement, the term “Out-of-Pocket Expenses” shall mean the amounts actually paid by Carlyle in cash in connection with its performance of the Services, including, without limitation, reasonable (i) fees and disbursements (including underwriting fees) of any independent auditors, outside legal counsel, consultants, investment bankers, financial advisors and other independent professionals and organizations, (ii) costs of any outside services or independent contractors such as financial printers, couriers, business publications or similar services and (iii) transportation, per diem, telephone calls, word processing expenses or any similar expense not associated with its ordinary operations. All reimbursements for Out-of-Pocket Expenses shall be made promptly upon or as soon as practicable after presentation by Carlyle to the Company of the statement in connection therewith.

The Company will indemnify and hold harmless Carlyle and its officers, employees, agents, representatives, members and affiliates (each being an “Indemnified Party”) from and against any and all losses, costs, expenses, claims, damages and liabilities (the “Liabilities”) to which such Indemnified Party may become subject under any applicable law, or

any claim made by any third party, or otherwise, to the extent they relate to or arise out of the performance of the Services contemplated by this Agreement or the engagement of Carlyle pursuant to, and the performance by Carlyle of the Services contemplated by, this Agreement. The Company will reimburse any Indemnified Party for all reasonable costs and expenses (including reasonable attorneys’ fees and expenses) as they are incurred in connection with the investigation of, preparation for or defense of any pending or threatened claim for which the Indemnified Party would be entitled to indemnification under the terms of the previous sentence, or any action or proceeding arising therefrom, whether or not such Indemnified Party is a party hereto, provided that, subject to the following sentence, the Company shall be entitled to assume the defense thereof at its own expense, with counsel satisfactory to such Indemnified Party in its reasonable judgment. Any Indemnified Party may, at its own expense, retain separate counsel to participate in such defense, and in any action, claim or proceeding in which the Company, on the one hand, and an Indemnified Party, on the other hand, is, or is reasonably likely to become, a party, such Indemnified Party shall have the right to employ separate counsel at the Company’s expense and to control its own defense of such action, claim or proceeding if, in the reasonable opinion of counsel to such Indemnified Party, a conflict or potential conflict exists between the Company, on the one hand, and such Indemnified Party, on the other hand, that would make such separate representation advisable. The Company agrees that it will not, without the prior written consent of the applicable Indemnified Party, settle, compromise or consent to the entry of any judgment in any pending or threatened claim, action or proceeding relating to the matters contemplated hereby (if any Indemnified Party is a party thereto or has been actually threatened to be made a party thereto) unless such settlement, compromise or consent includes an unconditional release of the applicable Indemnified Party and each other Indemnified Party from all liability arising or that may arise out of such claim, action or proceeding. Provided that the Company is not in breach of its indemnification obligations hereunder, no Indemnified Party shall settle or compromise any claim subject to indemnification hereunder without the consent of the Company. The Company will not be liable under the foregoing indemnification provision to the extent that any loss, claim, damage, liability, cost or expense is determined by a court, in a final judgment from which no further appeal may be taken, to have resulted solely from the gross negligence or willful misconduct of Carlyle. If an Indemnified Party is reimbursed hereunder for any expenses, such reimbursement of expenses shall be refunded to the extent it is finally judicially determined that the Liabilities in question resulted solely from the gross negligence or willful misconduct of Carlyle.

This Agreement shall be in effect on the date hereof and shall continue until such time as Carlyle or one or more of its affiliates collectively control, in the aggregate, less than 10% of the equity interests of the Company, or such earlier time as the Company and Carlyle may mutually agree. The provisions of Sections 5 and 8 and otherwise as the context so requires shall survive the termination of this Agreement.

Nothing herein shall in any way preclude Carlyle or its officers, employees, agents, representatives, members or affiliates from engaging in any business activities or from

performing services for its own account or for the account of others, including for companies that may be in competition with the business conducted by the Company.

(a) No amendment or waiver of any provision of this Agreement, or consent to any departure by either party from any such provision, shall be effective unless the same shall be in writing and signed by the parties to this Agreement, and, in any case, such amendment, waiver or consent shall be effective only in the specific instance and for the specific purpose for which given.

(b) This Agreement and the rights of the parties hereunder may not be assigned without the prior written consent of the parties hereto; provided, however, that Carlyle may, at its sole discretion, assign or transfer its duties or interests hereunder to its affiliates.

(c) Any and all notices hereunder shall, in the absence of receipted hand delivery, be deemed duly given when mailed, if the same shall be sent by registered or certified mail, return receipt requested, and the mailing date shall be deemed the date from which all time periods pertaining to a date of notice shall run. Notices shall be addressed to the parties at the following addresses:

(d) This Agreement shall constitute the entire agreement between the parties with respect to the subject matter hereof, and shall supersede all previous oral and written (and all contemporaneous oral) negotiations, commitments, agreements and understandings relating hereto.

(e) This Agreement shall be governed by, and enforced in accordance with, the laws of the State of New York (excluding the choice of law principles thereof). Each of the Parties hereby irrevocably and unconditionally consents to submit to the exclusive jurisdiction of the courts of the State of New York and of the United States of America, in each case located in the County of New York, in any action or proceeding arising out of or relating to this Agreement. This Agreement shall inure to the benefit of, and be binding upon, Carlyle and the Company (including any present or future subsidiaries of the Company that are not signatories hereto), and their respective successors and assigns.

(f) This Agreement may be executed in multiple counterparts, and by different parties on separate counterparts. Each set of counterparts showing execution by all parties shall be deemed an original, and shall constitute one and the same instrument.

(g) The waiver by any party of any breach of this Agreement shall not operate as or be construed to be a waiver by such party of any subsequent breach.

[signature page to follow]

IN WITNESS WHEREOF, the parties have caused this Agreement to be executed and delivered by their duly authorized officers or agents as set forth below.