Looks like it is an issue they aren't fixing just now: http://entityframework.codeplex.com/workitem/683
Couple of things you could try.
- Disable lazy loading for the entity by removing virtual
- Do the addition the other way around if applicable
For point 2, would be a case of exposing the DeviceId on your log table, and instead of doing:
device.Logs.Add(newEntry);
would to do something like:
newEntry.DeviceId = _deviceId;
context.Logs.Add(newEntry);