I changed this to a doc issue for 2.6/3.0 whenever.

I have two objections to adding "An empty deque evaluates as false". 
First, it implies (falsely) that it could be otherwise; since deque has
no __bool__ method, its __len__ method is used, so that bool(d) ==
(len(d)!=0).   Second, it misses better doc enhancements that might make
the statement I just made clearer and easier to find.

1. Ref manual Expressions Boolean Operations says
"In the context of Boolean operations, and also when expressions are
used by control flow statements, the following values are interpreted as
false: False, None, numeric zero of all types, and empty strings and
containers (including strings, tuples, lists, dictionaries, sets and
frozensets)."

For 3.0, I suggest replacing "and empty strings..." with
"empty strings and sequences (including strings, bytes, bytearrays,
tuples, lists, and Userlists and deques from the collections module),
and other empty containers (sets, frozensets, dictionaries, and
Userdicts and defaultdicts from the collections module)."
Anything else I forgot?  Adjust for 2.5/6.

The sentence after next "User-defined objects can customize their truth
value by providing a __bool__() method." should say '... __bool__ or
__len__ method.', with __len__ linked to object.__len__ just as __bool__
is linked to object.__bool__.

2. The LibRef entry for built-in function bool says simply "Convert a
value to a Boolean, using the standard truth testing procedure". 
Extended that with " described in the Language reference in the __bool__
and __len__ entries of the Special methods subsection and in the Boolean
operations subsection."