What error to raise when class state is invalid?

I find RuntimeError the most appropriate of all built-in exceptions to signal invalid state.

See this example of how it is used in CPython:

Python 2.7.10 (default, Jul 13 2015, 12:05:58)
[GCC 4.2.1 Compatible Apple LLVM 6.1.0 (clang-602.0.53)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from threading import Thread
>>> Thread().join()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/Cellar/python/2.7.10_2/Frameworks/Python.framework/Versions/2.7/lib/python2.7/threading.py", line 938, in join
    raise RuntimeError("cannot join thread before it is started")
RuntimeError: cannot join thread before it is started

It is important to notice that even the CPython implementation itself is not coherent about the use of specific exception types between libraries. Sometimes ValueError is used instead, however in my opinion its description from Python documentation shows that its use is reserved for other situations. RuntimeError is a more general exception and it should be used when a piece of code cannot behave correctly even if it was given proper input, which is somewhat similar to the situation when an object is in an invalid state.

ValueError is the best thing to raise in this case. For python, you should prefer using the built-in exception types over creating your own. You should only create new exception types when you expect that you will need to catch it and behave very differently than you'd behave when catching the builtin types. In this case, the situation shouldn't arise - you're not expecting to catch this because it would indicate an error in using the class in question. For this it's not worth creating a new type just to make it have another name - that's what the message string that you pass to ValueError() is for.

Is it possible to restructure your class so that such an invalid state is not possible?

I think the pythonic way is not leave the object in such a state where a method call will not crash despite being in an erroneous state. These are the hardest bugs to find, as the point where the program finally topples over is no where the bug occurred.

eg.

class PseudoTuple(object):
    """
The sum method of PseudoTuple will raise an AttributeError if either x or y have
not been set
"""
    def setX(self, x):
        self.x = x

    def setY(self, y):
        self.y = y

    def sum(self):
        """
In the documentation it should be made clear that x and y need to have been set
for sum to work properly
"""
        return self.x + self.y

class AnotherPseudoTuple(PseudoTuple):
     """
For AnotherPseudoTuple sum will now raise a TypeError if x and y have not been 
properly set
"""
    def __init__(self, x=None, y=None):   
        self.x = x
        self.y = y

What should not be done is something like

class BadPseudoTuple(PseudoTuple):
    """
In BadPseudoTuple -1 is used to indicate an invalid state
"""
    def __init__(self, x=-1, y=-1):
        self.x = x
        self.y = y

    def sum(self):
        if self.x == -1 or self.y == -1:
            raise SomeException("BadPseudoTuple in invalid state")
        else:
            return self.x + self.y

I think this comes under the pythonic motto of:

It's easier to ask for forgiveness than it is to get permission

If the exceptional state is something that can be expected to happen during the normal course of execution rather than being a user error by misusing the class then it seems reasonable that you should create your own exception. StopIteration and iterators are an example of this.

class InvalidOperationException(Exception):
    pass

SYS_STATE = 1

def something_being_run():
    if SYS_STATE < 2:
        raise InvalidOperationException

Something like that you mean ? I see no reason why you shouldn't sub-class exception to make your own Exception types, but that might just be the old Oracle PL/SQL Dev in me coming out...