Где бы вы ни декодировали исходную строку, она, скорее всего, была расшифрована латинским-1 или близким родственником. Поскольку latin-1 - это первые 256 кодовых точек Unicode, это работает:
>>> s = u'Gaga\xe2\x80\x99s'
>>> s.encode('latin-1').decode('utf8')
u'Gaga\u2019s'