Since 15 June 2017, Apple is requiring that all third-party apps syncing with iCloud must enforce app-specific passwords. This includes FullContact.
To create an app-specific password:
1) Go to https://appleid.apple.com/ and sign in.
2) Scroll down to Security, then click Generate Password under App-Specific Passwords.
3) Create an app-specific password for FullContact.
4) Copy and paste that password into the password field on FullContact when you connect your iCloud account.