Last first, you will get a months or up to three months free updates from tomtom via the internet on the update menu on the tom tom. After that you get some updates free but ones like road changes and speed camara places are all to pay for.
My tomtom had a diferent code to punch in when I connected mine to the phone. Check your paperwork that came with the unit to make sure it is not something other than 0000.
Try doing the search for your phone from the tomtom instead of the phone looking for it.
Hope this helps you.