Problema com acentuação

Vi que vários colegas já postaram e inclusive meu problema é igual ao de outro colega porém nenhuma solução deu certa ou foi muito clara, talvez por erro de código meu ou não entendimento por minha parte. Estou usando o python 2.7, na programação os acentos funcionam e na hora de armazenar as variaveis (preencher nome na lista por exemplo) é possível imprimir com os acentos , mas quando rodo o programa, os acentos que eu coloquei no print ficam com problema

Aqui o código:

# -*- coding: utf-8 -*-

import re

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

def listar(nomes):
    print 'Listando nomes:'
    for nome in nomes:
        print nome

def remover(nomes):
    print 'Qual nome gostaria de remover?'
    nome = raw_input()
    if(nome in nomes):
        nomes.remove(nome)
    else:
        print 'Nome nao consta na lista'

def alterar(nomes):
    print 'Qual nome vc gostaria de alterar?'
    nome_a_alterar = raw_input()
    if(nome_a_alterar in nomes):
        posicao = nomes.index(nome_a_alterar)
           print 'Digite novo nome:'
           nome_novo = raw_input()
           nomes[posicao] = nome_novo
    else:
        print 'Nome nao consta na lista'

def procurar(nomes):
    print 'Digite nome a procurar:'
    nome_a_procurar = raw_input()
    if(nome_a_procurar in nomes):
        print 'Nome existe na lista'
    else:
        print "Nome %s nao esta cadastrado" % (nome_a_procurar)


def procurar_regex(nomes):
    print('Digite a expressão regular')
    regex = raw_input()
    nomes_concatenados = ' '.join(nomes)
    resultados = re.findall(regex, nomes_concatenados)
    print(resultados)


def menu():
    nomes = []
    escolha = ''
    while(escolha != '0'):    
        print 'Digite 1 para cadastrar, 2 para listar, 3 para remover, 4 para alterar algum nome da lista dos cadastrados, 5 ver se esta ou não na lista, 6 para pesquisar por parte do nome, 0 para terminar'

        escolha = raw_input()

        if(escolha == '1'):
            cadastrar(nomes)

        if(escolha == '2'):
            listar(nomes)

        if(escolha == '3'):
            remover(nomes)

        if(escolha == '4'):
            alterar(nomes)

        if(escolha == '5'):
            procurar(nomes)

        if(escolha == '6'):
            procurar_regex(nomes)

menu()

a opção 5 quando fala no menu "5 - ver se está ou não na lista" da problema na acentuação, fica um caracter esquisito no lugar, se precisar posso colocar print, talvez seja erro meu, nunca tinha mexido em python, tudo que sei veio do curso. Obrigado.