Usually when a method is accessed as some_instance.some_method(), python's descriptor protocol kicks in and calls some_method.__get__(), which returns a bound method. However, because the method has been replaced with an instance of the Deco class, that does not happen - because Deco is not a descriptor. In order to make Deco work as expected, it must implement a __get__ method that returns a bound copy of itself.
Implementation
Here's basic "do nothing" decorator class:
import inspect
import functools
from copy import copy
class Deco(object):
    def __init__(self, func):
        self.__self__ = None # "__self__" is also used by bound methods
        self.__wrapped__ = func
        functools.update_wrapper(self, func)
    def __call__(self, *args, **kwargs):
        # if bound to an object, pass it as the first argument
        if self.__self__ is not None:
            args = (self.__self__,) + args
        #== change the following line to make the decorator do something ==
        return self.__wrapped__(*args, **kwargs)
    def __get__(self, instance, owner):
        if instance is None:
            return self
        # create a bound copy
        bound = copy(self)
        bound.__self__ = instance
        # update __doc__ and similar attributes
        functools.update_wrapper(bound, self.__wrapped__)
        # add the bound instance to the object's dict so that
        # __get__ won't be called a 2nd time
        setattr(instance, self.__wrapped__.__name__, bound)
        return bound
To make the decorator do something, add your code in the __call__ method.
Here's one that takes parameters:
class DecoWithArgs(object):
    #== change the constructor's parameters to fit your needs ==
    def __init__(self, *args):
        self.args = args
        self.__wrapped__ = None
        self.__self__ = None
    def __call__(self, *args, **kwargs):
        if self.__wrapped__ is None:
            return self.__wrap(*args, **kwargs)
        else:
            return self.__call_wrapped_function(*args, **kwargs)
    def __wrap(self, func):
        # update __doc__ and similar attributes
        functools.update_wrapper(self, func)
        return self
    def __call_wrapped_function(self, *args, **kwargs):
        # if bound to an object, pass it as the first argument
        if self.__self__ is not None:
            args = (self.__self__,) + args
        #== change the following line to make the decorator do something ==
        return self.__wrapped__(*args, **kwargs)
    def __get__(self, instance, owner):
        if instance is None:
            return self
        # create a bound copy of this object
        bound = copy(self)
        bound.__self__ = instance
        bound.__wrap(self.__wrapped__)
        # add the bound decorator to the object's dict so that
        # __get__ won't be called a 2nd time
        setattr(instance, self.__wrapped__.__name__, bound)
        return bound
An implementation like this lets us use the decorator on methods as well as functions, so I think it should be considered good practice.