Hi All - I recently upgraded to Windows 8 and encountered this problem. Very unhappy. However, I copied over the stuff under my old \users\(username)\AppData\Roaming\FamilyTreeMaker directory per the earlier post, and then TreeSync worked perfectly again, saying they were in sync! I even made a modest change and did a test sync and it worked! Very happy. So thanks to everyone who shared this tip.
Let me tell you what I did, in case anyone else hits this. First, I restored my family tree maker directory (and media directory), although to a different directory than before. I then reinstalled family tree maker 2012. Then I ran it and discovered the problem. Then I shut down FTM. When I did my Windows 8 upgrade it put all the old user settings under c:\windows.old\users\(old username)\AppData\Roaming\FamilyTreeMaker. I copied all of that into c:\users\(new username)\AppData\Roaming\FamilyTreeMaker and it worked.
They really should make this easier and more automatic, since it definitely can be done. Especially if you're doing something common like moving computers!!
C'mon ancestry.com folks, please fix this, as a lot of your users will have great unhappiness and difficulty encountering this.