Sorted it, but it was quite a major refactor.
The issue was that each service received it's own instance of 'context', so when two entities from two services were expected to work together, they wouldn't as each belonged to a different context.
One solution would have been to make the class that created the context a 'Singleton' so that it always returned the same instance, but that would have been very BAD as every page would then use the same context.
Each service got it's own instance of 'context' through Dependency Injection. I changed the project so only the controllers got an instance of context through DI. Then, in the controller constructor, this context was passed to the services that the controller had received through dependency injection.
This way, each request only ever uses a single instance of context, but this instance is still short lived, as it is supposed to be as each request has its own context and doesn't share one.
Not sure this is the way it is supposed to work, but given the web app I was working with, this seemed to be the best solution.
I also had to go through and add a 'context.SaveChanges();' statement everywhere a change to the database was made.
Not sure why this should be when the old version of EF did this automatically, but it now works.
Thanks for the advice Derrick