Checked this out more throughly and I came to the conclusion this cannot
be fixed without a considerable amount of work.

The problem is pickle adds an Node instance stub in the next_nodes set
before its attributes are ready. Since the stub doesn't have any
attribute at the time its added to the set, the __hash__ method fails
with an AttributeError exception.

To fix this, pickle would need to detect cyclic objects with a custom
__hash__ method; and when it would see one, it would need to emit POP
opcodes to revert the parts of the object already pickled. And then,
pickle would have to re-pickle the cyclic object using a special
procedure that would delay the use of __hash__ until all the attributes
of the object are ready to be used.

I do not believe the bug arises frequently enough to justify adding more
tricky code to pickle. So, I will not fix this myself (feel free to
write a patch, however).

Finally, you can workaround the bug using the __getstate__/__setstate__
mechanism as follow:

class Node(object):
  def __init__(self, i):
    self.i = i
    self.next_nodes = set()
  def __cmp__(self, other):
	return cmp(self.i, other.i)
  def __hash__(self):
    return hash(self.i)
  def __getstate__(self):
    next_nodes = self.next_nodes.copy()
    next_nodes.discard(self)
    return {'i': self.i,
            'self_in_next_nodes': self in self.next_nodes,
            'next_nodes': next_nodes}
  def __setstate__(self, state):
    if state.pop('self_in_next_nodes'):
        self.__dict__.update(state)
        state['next_nodes'].add(self)
    else:
        self.__dict__.update(state)

n = Node(12)
n.next_nodes = set([n])