João,

Vc tem que importar a biblioteca das expressões regulares, "import re", escrevi a baixo como deveria ficar seu script, mais informações, http://turing.com.br/material/regex/python_re.html

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

#python/app.py

import re 
#OBS VC TEM QUE IMPORTAR A BIBLIOTECA DO REGEX
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 deletar(nomes):
    print 'digite o nome a deletar:'
    nome = raw_input()
    nomes.remove(nome)

def alterar(nomes):
    print 'Digite o nome para alterar:'
    nome_a_alterar = raw_input()

    if (nome_a_alterar in nomes):
        posicao = nomes.index(nome_a_alterar)
        print 'digite o novo nome:'
        novo_nome = raw_input()
        nomes[posicao] = novo_nome
    else:
        print 'o nome nao existe, tente novamente.'
        alterar(nomes)

def procurar(nomes):
    print 'Qual nome quer procurar?'
    nome_procurar = raw_input()

    if (nome_procurar in nomes):
        print 'O nome esta na lista'
    else:
        print 'O nome nao esta na lista'

def procurar_regex(nomes):
    print('Digite a expressao regular')
    regex = raw_input()
    nomes_concatenado = ' '.join(nomes)
    resultado = re.findall(regex, nomes_concatenado)
    print resultado



def menu():
    import re
    nomes = []
    escolha = []
    while(escolha != '0'):    
        print 'Digite: 1 para cadastrar, 2 para listar, 3 para deletar, 4 para alterar, 5 para procurar, 6 para prcurar, 0 para terminar'
        escolha = raw_input()
        if(escolha == '1'):
            cadastrar(nomes)

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

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

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

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

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

menu()

Eu importei ela, mas dentro do menu. Eu PRECISO importar ela fora de qualquer def?

Aqui para ser mais preciso.

def menu():
    import re
    nomes = []
    escolha = []
    while(escolha != '0'):   

João,

Do jeito que Vc fez ela fica no escopo da função menu. Como dito, no erro, ela tem que ter escopo global. Como fiz no meu exemplo, a primeira linha do script. Espero ter ajudado.