Necesitas la declaración de #encoding al principio.
Código Python:
Ver original# -*- coding: utf-8 -*-
string_as_bytes = "\xc2\xbfC\xc3\xb3mo estas?"
string_as_unicode = string_as_bytes.decode('utf-8')
print "String as bytes"
print repr(string_as_bytes)
print
print "String as unicode"
print repr(string_as_unicode)
print
print "String as bytes"
print string_as_bytes
print
print "String as unicode"
print string_as_unicode
Obviamente UTF-8 tiene que estar soportado por tu shell.