I've had exactly the same issue on a brand new Samsung The Frame TV. I just got off a call with Applecare, and we were unable to resolve the issue.
I found that I could go to the Samsung App Store settings, go to the Apple TV app and select the Reinstall option, which would then allow me to go back into the App and try to sign in again, only I would have the same result -- an endless spinning wheel which would last for hours, with no success.
The strange thing is if you sign into appleid.apple.com and check for authorised devices, the Samsung TV appears immediately after you sign in on the app, despite the app forever spinning.
I signed out of the app this morning because since I've had the TV (for about a month now) I haven't been able to rent movies, although it would let me watch any content that I had already downloaded. I am regretting signing out this morning, because now the app doesn't work at all.
I will note too that the TV does not have any pending software updates.