When add an entity to your objectContext, if the entity reference an other existing entity, but that entity is not in memory, you need to create a EntityKey like the following.

 var address = new Address();
 address.City = "SomeCity";
 address.AddressType = "Home";
 address.ModifiedDate = DateTime.Now;
 address.ContactReference.EntityKey = new EntityKey("PEF.Contacts", "ContactID", 709);
 
 context.AddToAddresses(address);
 context.SaveChanges();