The object cannot be deleted because it was not found in the ObjectStateManager

Question

It means that entity is not attached (it was not loaded by the same context instance). Try this:

protected MyEntities sqlEntities;

public virtual void Delete(TEntity entity)
{
    sqlEntities.Attach(entity);
    sqlEntities.DeleteObject(entity);
    sqlEntities.SaveChanges();
}

Just a small clarification on the answer by Ladislav Mrnka (which should be the accepted answer).

If like me, you've got code in a format like this:

using (var context = new MyDataContext())
{
    context.MyTableEntity.Remove(EntytyToRemove);
    var nrOfObjectsChanged = context.SaveChanges();
}

..then this what you want to do:

using (var context = new MyDataContext())
{
    // Note: Attatch to the entity:
    context.MyTableEntity.Attach(EntityToRemove);

    context.MyTableEntity.Remove(EntityToRemove);
    var nrOfObjectsChanged = context.SaveChanges();
}

Perhaps this seems obvious, but it was not clear to me initially that it is necessary to specify the entity to attatch to, and not just the context.

Just to propergate on Kjartans explanation:

I had:

public Project DeleteProject(int id)
    {
        using (var context = new Context())
        {
            var p = GetProject(id);
            context.Projects.Remove(p);
            context.SaveChanges();
            return p;
        }
    }

The problem is that I used my own method (GetProject()) to get the entity (hence using another context to load the entity):

public Project GetProject(int id)
    {
        using (var context = new Context())
        {
            var project = context.Projects
                .Include(p => p.Reports.Select(q => q.Issues.Select(r => r.Profession)))
                .Include(p => p.Reports.Select(q => q.Issues.Select(r => r.Room)))
                .SingleOrDefault(x => x.Id == id);
            return project;      
        }
    }

One solution could be to attach the loaded entity as Kjartan states, another could be mine solution, to load the entity within the same context:

public Project DeleteProject(int id)
    {
        using (var context = new Context())
        {
            var p = context.Projects.SingleOrDefault(x => x.Id == id);
            if (p == null)
                return p;

            context.Projects.Remove(p);
            context.SaveChanges();
            return p;
        }
    }

I know this question is quite old but none of the above worked for me since i was deleting registers from more than one class/service and each of of them was instantiating it's own database connection context.

What i did to solve it was to send the first created context to the rest of the classes/services that where going to access the database.

For example, my serviceA was going to delete some of it's registers and call serviceB and serviceC to do the same with their registers.

I would then delete my registers on serviceA and pass as a parameter the context created on the serviceA to serviceB and serviceC.