Error exception must derive from BaseException even when it does (Python 2.7)

Others have shown you how to fix your implementation, but I feel it important to point out that the behavior you are implementing is already the standard behavior of exceptions in Python so most of your code is completely unnecessary. Just derive from Exception (the appropriate base class for runtime exceptions) and put pass as the body.

class TestFailed(Exception):
    pass

Use __init__() instead of __new__() to "initialize" classes. In most cases overriding __new__ is not necessary. It is called before __init__ during object creation.

See also Python's use of __new__ and __init__?

__new__ is a staticmethod that needs to return an instance.

Instead, use the __init__ method:

class TestFailed(Exception):
    def __init__(self, m):
        self.message = m
    def __str__(self):
        return self.message

try:
    raise TestFailed('Oops')
except TestFailed as x:
    print x