Amendment No. 6 to Transition Services Agreement among Verizon Information Technologies LLC, Hawaiian Telcom HoldCo, Inc., and Hawaiian Telcom Communications, Inc.

Exhibit 10.19

Stephen E. Smith

Vice President

December 15, 2005

James A. Attwood, Jr.

William Kennard

Hawaiian Telcom HoldCo, Inc.

Hawaiian Telcom Communications, Inc.

c/o The Carlyle Group

520 Madison Avenue, 41^st Floor

New York, NY 10022

R. Ronald Hopkinson

Latham & Watkins LLP

885 Third Avenue

Suite 1000

New York, NY 10022

Dear Sirs,

Reference is made to the Transition Services Agreement by and among Verizon Information Technologies LLC (successor to Verizon Information Technologies Inc.), Hawaiian Telcom HoldCo, Inc. (f/k/a Paradise HoldCo, Inc.), Hawaiian Telcom Communications, Inc. (f/k/a Paradise MergerSub, Inc.) and Verizon Hawaii Inc. dated May 21, 2004, as amended on August 30, 2004, April 8, 2005, April 28, 2005, August 29, 2005 and September 30, 2005 (herein the “Transition Services Agreement”). Capitalized terms used herein have the meanings assigned in the Transition Services Agreement or the Merger Agreement, as applicable, unless otherwise defined herein.

James A. Attwood, Jr.

R. Ronald Hopkinson

December 15, 2005

Page 2

1. Effect on Agreement. The provisions of Sections 13.1, 13.2, 13.3, 14.2(a), 14.2(b) and 14.2(c) are amended, modified and restated in their entirety as follows:

13.1. Term. This Agreement shall become effective as of the date first written above and shall, subject to Section 14.2, expire upon the earlier of 12:01 a.m. Eastern Standard Time on: (i) the date that a termination pursuant to Section 14.1 becomes effective and (ii) April 1, 2006 (the “Initial Term” and the “Cutover Time”). It is understood by the parties that Surviving Corporation shall be responsible, in accordance with Section 6.3, for all applicable costs and expenses incurred up to the Cutover Time. With respect to the Transition Services identified on Schedule A, C, and D, Supplier and its Affiliates shall commence providing such services on the Closing Date of the Merger (or, in the case of the service described in Schedule C, Section D-8, prior to such date as provided therein) and, subject to the terms and conditions hereof (including Section 13.2), shall provide each Transition Service for the remainder of the term hereof.

After 12:01 a.m. Eastern Standard Time on April 1, 2006, except in the circumstances contemplated by Section 14.2(b) or Section 14.2(c), Supplier shall cease to provide Surviving Corporation and its Affiliates any and all Transition Services, including without limitation, those described in Schedules A, B, C or D to this Agreement, and any type of “read only” access or other support type of access. Provided, however that after April 1, 2006, the Supplier will provide the financial information identified in Schedule A, B-1, paragraphs 1 through 4 as described therein, for accounting periods ending prior to the date of termination of the Initial Term for which such financial information has not previously been provided including but not limited to the accounting period ending March 31, 2006.

After the end of the Initial Term, Supplier shall forward to the Surviving Corporation information about certain recent transactions when and if received and to the extent Supplier has such capabilities, (For example, Supplier may receive a customer payment because the customer’s account payable system inappropriately retains Supplier’s billing address (“Trickle Cash”), or Supplier may receive a telco’s service usage record because the telco’s tables have not been changed to route usage records to Surviving Corporation (“Trickle Usage”)). Supplier shall commence the extract process promptly after the end of the Initial Term. Supplier currently estimates that it will require approximately two and a half days to complete such process.

13.3. Termination on Buyer Change of Control. Notwithstanding any other provision herein, including the provisions of Section 22.2, if a Buyer Change of Control occurs after the expiration of the Initial Term the term of this Agreement shall automatically expire, without further notice or action by Supplier.

14.2(a). Other than services terminated prior to December 1, 2005, the Surviving Corporation may not terminate any Transition Service after Closing and prior to the end

James A. Attwood, Jr.

R. Ronald Hopkinson

December 15, 2005

Page 3

of the Initial Term. Provisions of the Cutover Plan or other terms conditions or agreements to the contrary are deemed amended hereby.

14.2(b). For the avoidance of doubt, when all Transition Services cease to be provided hereunder, the Cutover shall occur. The Surviving Corporation acknowledges and agrees that it must be prepared to perform, or have other third parties perform on its behalf, all of the Transition Services without interruption upon the Cutover. Supplier agrees to reasonably cooperate in such planning and preparation and to reasonably cooperate in the transition of the Transition Services to the Surviving Corporation or its designee, including by performing the tasks assigned to it in the Cutover plan.

14.2(c). Not less than two (2) business days prior to the time of termination or expiration of the Initial Term of this Agreement, the Surviving Corporation shall have the right to give notice to Supplier that it elects to delay Cutover and continue to receive all of the Transition Services for any reason. If the Surviving Corporation gives such notice, then the parties shall delay the Cutover and agree that Supplier and its Affiliates shall continue to provide all Transition Services, other than those that had terminated prior to December 1, 2005, until such time as the Surviving Corporation can transition off of them (any such period until Holdover Cutover occurs a “Holdover Period”). After the commencement of the Holdover Period Surviving Corporation may terminate the Holdover Period upon sixty (60) days irrevocable prior written notice to Supplier which notice shall identify the termination time and one of the termination dates described in the next sentence. Termination of the Holdover Period shall occur at 12:01 a.m. Eastern Time on one of the following dates: July 29, 2006, August 26, 2006, September 30, 2006, November 30, 2006, a subsequent Saturday which is nearest to the end of a calendar month and which date has been mutually agreed upon by the parties being the termination date for the Holdover Period. Notwithstanding anything herein to the contrary Surviving Corporation may terminate the Holdover Period on May 27, 2006 at 12:01 a.m. Eastern Time by providing irrevocable prior written notice to Supplier on or before March 29, 2006. In the event of a Holdover Period, the Surviving Corporation shall pay to Supplier (i) in advance for each full or partial month of any Holdover Period, an amount equal to two (2) times the amount of the Service Fees (then in effect) payable for all Transition Services, it being understood and agreed that such rate is fair and reasonable, plus (ii) if applicable, interest for nonpayment at the Applicable Rate; provided, however, that Surviving Corporation shall only be required to pay the Service Fees applicable to Transition Services at the rates otherwise applicable prior to the Holdover Period if the delay in the Surviving Corporation’s transition off Transition Services is due to a Force Majeure Event (defined below) and then only for the shorter of such Force Majeure Event and 30 calendar days. After the end of any Holdover Period, Supplier shall cease to provide Surviving Corporation and its Affiliates any and all Transition Services. Provided, however that after the end of the Holdover Period, the Supplier will provide the financial information identified in Schedule A, B-1, paragraphs 1 through 4 as described therein, for all whole or partial months (not including Cutover date).

James A. Attwood, Jr.

R. Ronald Hopkinson

December 15, 2005

Page 4

2. Amendment of Schedule D Transition Services terms. Notwithstanding anything to the contrary in the Transition Services Agreement or the Schedules thereto (including without limitation the provisions of Schedule D, S-l, Section L), all Transition Services (other than those terminated by Surviving Corporation prior to December 1, 2005) shall be provided for the entire Initial Term, until April 1, 2006. Accordingly, the provisions pf Schedule D, S-l, Section L, and any other similar provisions are hereby amended such that the ISP Service Term shall expire at 12:01 a.m. Eastern Standard Time on April 1, 2006. Further, the Basic Service Fee and Base Service Fee provisions of Schedule D Transition Services are hereby amended as described on Amended Schedule D attached hereto and incorporated herein by this reference.

3. PIC Changes. In connection with correcting the error relating to the inadvertent switching of long distance customers in Hawaii of certain Verizon affiliates of Supplier to Surviving Corporation’s long distance carrier which was not the authorized carrier (the “Switching Error”), in connection with the Closing, Supplier (or one or more of its Affiliates) has incurred and shall incur all expenses to:

(a) notify affected customers of the error;

(b) handle, on or prior to November 4, 2005, customer inquiries associated with the notification of the Switching Error;

(c) process, on or before November 6, 2005, the bulk switching of customers affected by the Switching Error to their choice of long distance carriers; and

(d) calculate and remit bill credits or refunds from the Surviving Corporation to customers affected by the Switching Error.

The foregoing are collectively referred to as the “Actions.”

Such Actions shall be in full satisfaction of any and all liability of Seller and its Affiliates to the Surviving Corporation and its Affiliates for any losses, liabilities, damages, deficiencies, costs or expense (“Losses”) including, without limitation, any such Losses under (i) the Transition Services Agreement, (ii) the Agreement of Merger dated as of April 8, 2005, by and among Hawaiian Telcom Holdco, Inc. (f/k/a Paradise HoldCo, Inc.), a Delaware corporation; Hawaiian Telcom Communications, Inc. (f/k/a Paradise MergerSub, Inc.), a Delaware corporation; GTE Corporation, a New York corporation; and Verizon HoldCo LLC, a Delaware limited liability company, or (iii) any Ancillary Document. Each of the Surviving Corporation and its Affiliates releases Supplier and each of its Affiliates, and agrees not to make any claim against any of Supplier or its Affiliates, for any Losses arising directly or indirectly from, or relating to, the Switching Error, other than as may arise from Supplier’s (or any of its Affiliate’s) failure to perform the Actions set forth above in a commercially reasonable manner. As of the date hereof, the Surviving Corporation has no knowledge that any of the Actions has not been performed in a commercially reasonable manner.

James A. Attwood, Jr.

R. Ronald Hopkinson

December 15, 2005

Page 5

4. Data Extract Schedule. The parties acknowledge that Surviving Corporation previously agreed to receive a fifth full but unsynchronized data extract in December for a payment of $150,000. The parties have now agreed that December extract will be a full synchronized data extract. Such data extract will be provided after any known data/application upgrades scheduled through December 31^st 2005 have been implemented among Verizon West systems and will be provided to the Surviving Corporation no later than January 16^th 2006. Surviving Corporation will pay $500,000 for such extract. Such payment will be due immediately upon the execution of this Amendment.

In addition, Supplier shall provide Surviving Corporation with a sixth full but unsynchronized data extract for the month of February, 2006. The parties agree that the extract dates for data extract delivery for each application or group of applications for the sixth extract shall be as follows: Data extracts for applications with known upgrades scheduled for February 24^th, 2006 for implementation among Verizon West systems, will be provided no later than March 3, 2006. Extracts for any financial data requiring month-end-processing or extracts of applications with upgrades schedules after February 24, 2006 will be provided no later than March 13, 2006. The parties agree and acknowledge that the “February” data extracts will not be synchronized across applications and the results may vary from previously supplied data extracts. Surviving Corporation shall pay $350,000 for such extract. Such payment will be due to Supplier_with Surviving Corporation’s February 2006 fixed transition Services Agreement payment.

5. Payment of Certain Long Distance Fees. Immediately upon the execution of this Amendment, Surviving Corporation or its affiliate will pay Supplier the sum of $176,341 in satisfaction and payment for certain long distance fees (Usage above contract Thresholds and recurring fees) for invoiced rendered July 2005 through September 2005.

6. Reference is made to that Amended and Restated Agreement of Merger dated as of April 8, 2005. The parties hereby amend and restate in its entirety Section 5.30 thereof as follows:

5.30 Additional Transition Services. If during the Initial Term of the Transition Services Agreement (i.e., within nine months of the Closing Date), Buyer identifies any service which (i) is needed by Buyer to carry on the functional operation of the local telephone exchange and Internet access portions of the Business, (A) in all material respects, in compliance with Law and (B) in a manner consistent with the operation of such portions of the Business immediately prior to the Effective Time, (ii) was provided by Seller or one of its Affiliates (other than Company or the Subsidiaries) immediately prior to the Effective Time, (iii) is not among the services described in Section 3.24(a) and (iv) was requested by Buyer prior to the date hereof and refused or not granted by Seller, then Buyer and Seller agree that the Transition Services Agreement shall be amended to include such service for the balance of the Transition Services Agreement, and such service shall be offered at an amount equal to 50% of the fully loaded cost that would otherwise apply to such service, as such amount may be determined by Seller, acting reasonably, provided that during any period when the Surviving Corporation is required to pay two times (2x) for services under the Transition Services Agreement,

James A. Attwood, Jr.

R. Ronald Hopkinson

December 15, 2005

Page 6

such amount shall be increased to 200% of such fully loaded cost. Notwithstanding anything in this Section 5.30 to the contrary, Surviving Corporation shall not be entitled to request or obtain, and Supplier shall not be required to provide any additional Transition Service after the effective date of this Amendment.

7. Authority. Each of the Parties represents that it has all corporate power and authority to execute this letter agreement and has obtained any consent required to be obtained from any third party as a condition to its execution and delivery of this letter agreement.

Please indicate your acceptance of this amendment to the Agreement by having an authorized representative of Hawaiian Telcom Holdco, Inc. and Hawaiian Telcom Communications, Inc. sign below and returning a fully executed copy of this letter agreement to me.

Agreed to and accepted effective as of the date first set forth above.

Alan M. Oshima, Esq.