before restoring the phone as new, try erasing all the files in the lockdown folder. worked for me a couple times
and i did not have to erase and restore
other causes of lots of other is stuff being left on the iPod / iPhone when you switch to itunes match
i was unable to sync or backup my phones once because i had a 32 bit computer and apple came out with a 64 bit only iTunes and i had to download the special 32 bit iTunes version