EntityFramework 6 Creating new Record with existing foreign key error on Many-to-many relationships

So I Have two objects

// First Object
public class Record{
   public int RecordId { get; set;} 
    public virtual ICollection<Country> CountryCollection { get; set; }
}



// Second Object
public class Country{
   public int CountryId { get; set;} 
   public virtual ICollection<Record> Records{ get; set; } 
   [Index("UI_CountryName", IsUnique = true)] 
   public string CountryName { get; set; }
}

..

// And my map configuration
public class RecordMap: EntityTypeConfiguration<Record>
{
    HasMany(r => r.CountryCollection)
            .WithMany(c => c.Records)
            .Map(t => t.ToTable("RecordCountryMap","dbo").MapRightKey("CountryId").MapLeftKey("RecordId"));
}

So the issues arises when I try to insert new record into Record.CountryCollection with the following code

 newRevisionRec.CountryCollection = new Collection<Country>();
        foreach (var country in record.Countries)
        {
            newRevisionRec.CountryCollection.Add(new Country
            {
                CountryId = country.CountryId,
                CountryName = country.CountryName,
            });
        }

What's ends up happening is that every time I do this EF tries to create new Country record which a unique constraint exception. Any ideas on how to prevent countries from being saved?