I encountered a problem with Jerther's solution, in the situation where a relationship containing a Key Entry has been deleted, with this exception being thrown:
A relationship from the 'TableAValue_TableA' AssociationSet is in the 'Deleted' state. Given multiplicity constraints, a corresponding 'TableAValue_TableA_Source' must also in the 'Deleted' state.
The problem appears to be that RejectNavigationChanges() can't restore the deleted relationship to its previous state, because it contains a Key Entry, but the associated objects have already been restored by RejectScalarChanges().
The solution is to change the way RejectScalarChanges() restores deleted entities, to using entry.Reload().
My working solution:
public void RejectChanges()
{
    RejectScalarChanges();
    RejectNavigationChanges();
}
private void RejectScalarChanges()
{
    var changedEntries = _dbContext.ChangeTracker.Entries()
        .Where(e => e.State != EntityState.Unchanged);
    foreach (var entry in changedEntries)
    {
        switch (entry.State)
        {
            case EntityState.Added:
                entry.State = EntityState.Detached;
                break;
            case EntityState.Modified:
                entry.State = EntityState.Unchanged; 
                break; 
            // Where a Key Entry has been deleted, reloading from the source is required to ensure that the entity's relationships are restored (undeleted).
            case EntityState.Deleted:
                entry.Reload();
                break;
        }
    }
}
private void RejectNavigationChanges()
{
    var objectContext = _dbContext.GetObjectContext();
    var addedRelationships = objectContext.ObjectStateManager.GetObjectStateEntries(EntityState.Added)
        .Where(e => e.IsRelationship);
    var deletedRelationships = objectContext.ObjectStateManager.GetObjectStateEntries(EntityState.Deleted)
        .Where(e => e.IsRelationship && !RelationshipContainsKeyEntry(e));
    foreach (var relationship in addedRelationships)
        relationship.Delete();
    foreach (var relationship in deletedRelationships)
        relationship.ChangeState(EntityState.Unchanged);
    bool RelationshipContainsKeyEntry(ObjectStateEntry stateEntry)
    {
        var keys = new[] { stateEntry.OriginalValues[0], stateEntry.OriginalValues[1] };
        return keys.Any(key => objectContext.ObjectStateManager.GetObjectStateEntry(key).Entity == null);
    }
}