__new__ being static method allows a use-case when you create an instance of a subclass in it:
return super(<currentclass>, cls).__new__(subcls, *args, **kwargs)
If new is a class method then the above is written as:
return super(<currentclass>, cls).new(*args, **kwargs)
and there is no place to put subcls.
I don't really see when that would be a proper use of __new__, though. Maybe I'm not seeing it, but that just seems to me to be a completely pathological use of it (and it should be said, that if you still really want it, then you could access it with object.__new__.__func__). At the very least, I find it very hard to imagine that it would have been the reason for Guido to change __new__ from being a class method to a static method.
A more common case would be to call parent __new__ without using super(). You need a place to pass cls explicitly in this case:
class Base(object):
    @classmethod
    def new(cls):
        print("Base.new(%r)" % (cls,))
        return cls()
class UseSuper(Base):
    @classmethod
    def new(cls):
        print("UseSuper.new(%r)" % (cls,))
        return super(UseSuper, cls).new() # passes cls as the first arg
class NoSuper(Base):
    @classmethod
    def new(cls):
        print("NoSuper.new(%r)" % (cls,))
        return Base.new()  # passes Base as the first arg
class UseFunc(Base):
    @classmethod
    def new(cls):
        print("UseFunc.new(%r)" % (cls,))
        return Base.new.im_func(cls)  # or `.__func__(cls)`. # passes cls as the first arg
print(UseSuper.new())
print('-'*60)
print(NoSuper.new())
print('-'*60)
print(UseFunc.new())