I've recently updated my iPhone and paired it to my Columbus unit, deleting the old phone in the process.

Now whenever the phone connects I get a message saying "a new telephone book is available".

Pressing OK makes no difference, same message next time I get in the car.

 

Yes I have tried to update address book via Maxidot

No I haven't tried to re-pair the phone. Other than this is there anything else I should try?

All it means is the Columbus has downloaded the phone book, and is telling you it's done so. It does it every time, nothing wrong there.

OK thanks, strange though. It didn't keep doing it with my old phone.

Not sure, but mine always informs me when I connect and it updates the phonebook.