Multiplicity conflicts with the referential constraint

Another way to determine the root of the problem is the following :

1. open the .edmx file and find the entity containing the foreign key field.
2. find the property that is causing the error message and right click to open the context menu.
3. click properties on the context Menu to open the properties window.
4. Examine the Nullable property for the field and change it to the appropriate value.

This can happen if your configuration and your model do not match.

Let's say in your db configuration you have a rule like this:

protected override void OnModelCreating(DbModelBuilder modelBuilder)
{
    modelBuilder.Entity<Agent>().HasRequired(x=>x.MailingAddress);
    //..

But in your model you say that MailingAddress is optional:

public int? MailingAddressId { get; set; }

I believe the issue has something to do with the fact that Agent has more than one property of type Address and possibly also because one of them is nullable

It's not the case.

For database first: if you altered an existing table already added to Entity Framework, say added a foreign key constraint after the fact, delete the table in the EDMX designer and add again and this will resolve the error.