1. Do a full reset. Put the camera back to all factory defaults. Then double check all the menu entries (especially AF fine tune) to ensure everything is zero'd out.
2. Call Nikon and tell them that you're having a service completion problem. Ask to speak with the head of service to explain the matter and then tell him or her that you want the camera operating within spec. A request to the head of service to follow the trouble ticket and service procedure to ensure proper completion is also advisable.
3. Get your authorization and send in the camera. Include in the insured shipping package a letter that re-states your conversation with the head of service. As a general rule, I personally wouldn't bother complaining or pointing out any perceived failures on Nikon's part. As right as I might be in the same situation, dressing them down wouldn't help my case.
4. With the direct name and address of the head of service, write a letter re-detailing the problems, add a request to replace the camera if it cannot be brought reliably into spec, and then transmit the letter by registered mail or by courier.