Encoding no python

Olá a todos, tudo certo?
Durante o curso de python, aprendemos a respeito de um cabeçalho que ajusta a codificação de caracteres para UTF-8 ou outras codificações.
No entanto, mesmo com o cabeçalho, o erro inda persiste, principalmente quando uso a função print.
Segue meu arquivo app.py para análise: 

# -*- coding: UTF-8 -*-

#python /app.py

def cadastrar(nomes):
    print 'Digite o nome a ser cadastrado'
    nome = raw_input()
    nomes.append(nome)

def remover_nome(nomes):
    print 'Qual o nome você gostaria de remover?'
    nome = raw_input()
    nomes.remove(nome)

def alterar_nome(nomes):
    print 'Qual o nome dalista gostaria de alterar?'
    nome_antigo = raw_input()
    if nome_antigo in nomes:
        print 'Digite o novo nome'
        novo_nome = raw_input()
        indice_do_nome_antigo = nomes.index(nome_antigo)
        nomes [indice_do_nome_antigo] = novo_nome
    else:
        print 'Nome não encontrado. Tente novamente'

def procurar(nomes):
    print 'digite o nome a ser pesquisado na lista'
    nome_procurado = raw_input()
    if nome_procurado in nomes:
        print 'achei!'
    else:
        print 'Nome não existe'

#Funcao menu

def menu():
    nomes = []
    escolha = ''
    while escolha != '0':
        print 'Digite 1 para cadastrar um novo nome, 2 para exibir os nomes cadastrados, 3 para remover um nome já cadastrado, 4 para alterar um nome existente da lista,  5 para pesquisar por um nome e 0 para terminar o programa'
        escolha = raw_input()
        if escolha == '1':
            cadastrar(nomes)
        elif escolha == '2':
            listar(nomes)
        elif escolha == '3':
            remover_nome(nomes)
        elif escolha == '4':
            alterar_nome(nomes)
        elif escolha == '5':
            procurar(nomes)
    print "Fim!"

def listar(lista_de_nomes):
    for nome in lista_de_nomes:
        print nome

menu()

Desde já agradeço.