Чтобы избежать проблем при работе с отключенными сущностями (Disconnected Entities) вам нужно использовать не только Navigation Properties но и связи на основе внешнего ключа ( foreign key associations), для этого сделайте вашу модель такой:
public class Product
{
public int Id { get; set; }
public string Name { get; set; }
public virtual Category Category { get; set; }
public int CategoryId { get; set; }
}
Подробнее можно прочитать в книге "Programming Entity Framework" Julia Lerman, 85 страница раздел "Working with Relationships with and Without Foreign Keys"
