I'd use this only because I find 2 lines of code easier to read than all of the others above.
var itemsToRemove = oldList.Except(newList).ToArray();
var itemsToAdd = newList.Except(oldList).ToArray();
This will work as long as each list is actually a set. Given your description of the original problem, it sounds like this is true.
