When creating a domain pair, the following error is received: Cannot connect to the specified domain controller. Credentials are invalid (4315330)

When trying to create a domain pair the following error is received:

Cannot connect to the specified domain controller. Credentials are invalid

The service account  is in the built-in administrators group in both the target and source but when you  try to logon to the Domain Controller,  using the service account it fails to logon and you receive the error message:

Your account is configured to prevent you from using this computer.

This particular problem can be caused because the Service Account has "Workstation Restrictions" enabled on the account in the Domain.

To set workstation restrictions for a user, open the Microsoft Management Console (MMC) Active Directory Users and Computers snap-in, right-click the user's account, then select Properties. In the Properties dialog box, click the Account tab, then click Log On To to display the dialog box that contains the Computers the account can only log on to.