> I have a lock that may or may not be currently held when I release it, 
> and now I know I can just catch RuntimeError in that case.

Only if you're willing to make assumptions about the threading model and the source of locks.  And I fear the current change overpromises.

For example, the LockType from _dummy_thread raises an error not based on RuntimeError, and has comments suggesting it might stop raising entirely.  I believe I have seen other Lock-emulation code which also does not raise an error, though the closest I can come to finding it right now is logging_releaseLock() when the import of either _thread or threading failed.

Starting with http://hg.python.org/cpython/file/acea9d95a6d8/Doc/library/threading.rst

I would prefer to change to following two sentences:

    If an attempt is made to release an unlocked lock, a :exc:`RuntimeError` will be raised.
...
    When invoked on an unlocked lock, a :exc:`ThreadError` is raised.

in any of the following ways:

(a) Change "will be"/"is" --> "may be", so it isn't promised:

    If an attempt is made to release an unlocked lock, a :exc:`RuntimeError` may be raised.
...
    When invoked on an unlocked lock, a :exc:`ThreadError` may be raised.

(b) Clarify that it is implementation-specific

    If an attempt is made to release an unlocked _thread.lock, a :exc:`RuntimeError` will be raised.
...
    When invoked on an unlocked _thread.lock, a :exc:`ThreadError` is  raised.

(and add to the caveats)
    Locks provided by other modules may have slightly different behavior, particularly when an an operation fails.  For example, unlocking without first acquiring may raise a different error, or may not raise at all.

(c) Clarify that alternatives are buggy (and fix those in the stdlib)
    If an attempt is made to release an unlocked lock, a :exc:`RuntimeError` will be raised.
...
    When invoked on an unlocked lock, a :exc:`ThreadError` is be raised.


(and add to the caveats)
    Historically, many Locks have followed a slightly different contract, particularly when an an operation fails.  For example, unlocking without first acquiring might raise a different error, or might not even raise at all.