Configure failover failed. Error: 20114: The DHCP Failover relationship already exists.
Despite removing the scopes from DHCP failover the partner server still believes the DHCP failover relationship was in existence.
After messing around a little longer I found out a work around. The error was occurring because I was using the same Relationship Name as before. Changing the Relationship Name to something else resolves the issue.