The documentation for __new__ at http://docs.python.org/reference/datamodel.html#object.__new__ is:
"""
object.__new__(cls[, ...])
Called to create a new instance of class cls. __new__() is a static method (special-cased so you need not declare it as such) that takes the class of which an instance was requested as its first argument. The remaining arguments are those passed to the object constructor expression (the call to the class). The return value of __new__() should be the new object instance (usually an instance of cls).

Typical implementations create a new instance of the class by invoking the superclass’s __new__() method using super(currentclass, cls).__new__(cls[, ...]) with appropriate arguments and then modifying the newly-created instance as necessary before returning it.

If __new__() returns an instance of cls, then the new instance’s __init__() method will be invoked like __init__(self[, ...]), where self is the new instance and the remaining arguments are the same as were passed to __new__().

If __new__() does not return an instance of cls, then the new instance’s __init__() method will not be invoked.

__new__() is intended mainly to allow subclasses of immutable types (like int, str, or tuple) to customize instance creation. It is also commonly overridden in custom metaclasses in order to customize class creation.
"""


The problem is in this line: "If __new__() returns an instance of cls, then the new instance’s __init__() method will be invoked like __init__(self[, ...]), where self is the new instance and the remaining arguments are the same as were passed to __new__()."

This is only true in the context of a constructor. In particular, directly calling cls.__new__(cls) will NOT call __init__.

If I define a class:
  
class C(object):
  def __new__(*args, **kwargs):
    print 'new', args, kwargs
    return object.__new__(*args,**kwargs)
  def __init__(self):
    print 'init'

C() will result in __new__ and __init__ being both executed, but C.__new__(C) will only create the instance of C; it will not call __init__!

The original documentation described in http://bugs.python.org/issue1123716 was more correct:

"__new__ must return an object... If you return an
existing object, the constructor call will still call
its __init__ method unless the object is an instance of
a different class..."

That is __init__ is only being called in the context of an external constructor call.  

Proposed phrasing:
"If __new__() is invoked during object construction (cls()) and it returns an instance of cls, then the new instance’s __init__() method will be invoked like __init__(self[, ...]), where self is the new instance and the remaining arguments are the same as were passed to the object constructor."

Whether or not the current language is technically correct, I would support improving its clarity.

Would you like to create a formal patch?  Also, note that the newest documentation is published here:

http://docs.python.org/dev/reference/datamodel.html#object.__new__

(Note that in the future, you do not need to post such full excerpts, just the key parts.)

Since this has taken long on the tracker, I just opened a PR with proposed changes from Aaron.

FWIW, the underlying code for this in Objects/typeobject.c::type_new().

New changeset 6b16d938d6d1ccb443815e20e8812deed274dc09 by Raymond Hettinger (Joannah Nanjekye) in branch 'master':
bpo-15542: Documentation incorrectly suggests __init__ called after direct  __new__ call (GH-15478)
https://github.com/python/cpython/commit/6b16d938d6d1ccb443815e20e8812deed274dc09

New changeset c841fb9e065c393bba5d5505238f7e286f1dcfc6 by Raymond Hettinger (Miss Islington (bot)) in branch '3.8':
bpo-15542: Documentation incorrectly suggests __init__ called after direct  __new__ call (GH-15478) (GH-15506)
https://github.com/python/cpython/commit/c841fb9e065c393bba5d5505238f7e286f1dcfc6

Thanks everyone.