Solved
Got my devices signed and working with Apple TV now. Here is the process that worked for me.
1. Uninstall Apple TV from device
2. Remove power for 30 seconds
3. Install Apple TV app
4. Launch Apple TV and select "Sign In Later"
5. Navigate to the Cog setting and Select Accounts -> Sign-in
6. Use the QR code to sign-in