Использовать строки Unicode:
# coding: cp1252
print u"é".capitalize()
# Prints É
Если все, что у вас есть, это 8-битная строка, сначала декодируйте ее в Unicode:
# coding: cp1252
print "é".decode('cp1252').capitalize()
# Prints É
Если вам снова понадобится 8-битная строка, закодируйте ее:
# coding: cp1252
print "é".decode('cp1252').capitalize().encode('cp1252')
# Prints É (assuming your terminal is happy to receive cp1252)