Hola que tal!
Anteriormente ya había hecho esta "Agenda", lo que hice ahora fue mejorarla (Ohhh :O.... xD)
Bien que tiene de nuevo... pues si usaron la versión anterior de mi "Agenda" podrán notar algunos cambios, bien aquí la lista de las mejoras:
[+]Se agrego el campo E-mail

[+]Se mejoro la lectura de los Contactos

[+]Se mejoro la búsqueda de los contactos
Entre otras cosillas mas... :)

Bien para usar esta agenda necesitan usar la librería que nos ayudara a conectar con MySQL, para ello usaremos los siguientes comandos:

apt-get install python-mysqldb

En fedora sería algo como:

yum install MySQL-python.i686

También es necesario haber creado la base de datos con el Nombre que quieran, solo importante dentro de la tabla crear los campos "nombre" , "telefono" e "mail", primero nos logeamos en MySQL y despues creamos la DataBase...

#[1]DESPUES DE -u INTRODUCIMOS EL USER
#[2]DAMOS ENTER E INTRODUCIMOS LA PASS
mysql -u root -p;
create database contactos;
use contactos;
create table contactos(nombre varchar(50),pass varchar(25),mail varchar(30));

Eso seria la base de datos para poder hacer funcionar nuestro "Programa"...
También pueden crear esta tabla desde su navegador, ya depende de cada quien, para mi es mas rápido en la consola :D

Bien después de crear la base de datos con la tabla respectiva es posible usar la agenda.
Bien pues aquí el code:

#!/usr/bin/Python

###########################
#AGENDA EN PYTHON V 1.5   #
#BY [Z]tuX                #
#http://ztux.blogspot.com/#
###########################

import MySQLdb, os

def agregar(server,user,passwd,bd):
    db = MySQLdb.connect(server,user,passwd,bd)
    cursor = db.cursor()
    name = raw_input('[+]Nombre: ')
    telefono = raw_input('[+]Telefono: ')
    mail= raw_input('[+]E-Mail: ')
    cursor.execute("insert into contactos (nombre,telefono,mail) values ('%s','%s','%s')"%(name,telefono,mail))
    print 'Datos agregados correctamente...'
    cursor.fetchall()
    cursor.close()
    raw_input("> Press Enter...")
    run()
def ver (server,user,passwd,bd):
    try:
        db = MySQLdb.connect(server,user,passwd,bd)
        ztux = db.cursor()
        ztux.execute("select * from %s "%(bd))
        a = ztux.fetchall()
        for i in a: #Se crea una lista en la variable i
           if i=='':
               print "No hay contactos..."
           else:
               print '[+]Nombre:',i[0],'\n[+]Telefono:',i[1],'\n[+]E-Mail:',i[2],"\n----------"  #Mostramos La lista
        ztux.close()
        raw_input("> Press Enter...")
        run()
    except:
        print '[*]Error al conectar a la base de Datos...\n'
        run()
    
def buscar(server,user,passwd,bd):
    try:
        db = MySQLdb.connect(server,user,passwd,bd)
        buscar = raw_input('[+]Nombre del contacto: ')
        ztux = db.cursor()
        ztux.execute("select * from %s where nombre='%s'"%(bd,buscar))
        a = ztux.fetchall()
        for i in a:
            print '[+]Nombre:',i[0],'\n[+]Telefono:',i[1],'\n[+]E-Mail:',i[2]
        ztux.close()
        raw_input("> Press Enter...")
        run()
    except:
        print '[*]Error al conectar a la base de Datos...\n'
        run()
        
def editar(server,user,passwd,bd):
    try:
        db = MySQLdb.connect(server,user,passwd,bd)
        print '[1]Nombre\n[2]Telefono\n[3]E-mail\n[+]Regresar'
        opc =raw_input('Que desas editar: ')
        if opc=='1':
            editar = raw_input('[+]Nombre del contacto a editar: ')
            cambiar = raw_input('[+]Escribe el nuevo nombre del contacto: ')
            ztux = db.cursor()
            ztux.execute("update %s set nombre='%s' where nombre='%s'"%(bd,cambiar,editar))
            ztux.close()
            print 'Contacto Actualizado...'
            raw_input("> Press Enter...")
            run()
        elif opc=='2':
            editar = raw_input('[+]Nombre del contacto a editar: ')
            cambiar = raw_input('[+]Escribe el nuevo numero del contacto: ')
            ztux = db.cursor()
            ztux.execute("update %s set telefono='%s' where nombre='%s'"%(bd,cambiar,editar))
            ztux.close()
            print 'Contacto Actualizado...'
            raw_input("> Press Enter...")
            run()
        elif opc=='3':
            editar = raw_input('[+]Nombre del contacto a editar: ')
            cambiar = raw_input('[+]Escribe el nuevo e-mail del contacto: ')
            ztux = db.cursor()
            ztux.execute("update %s set mail='%s' where nombre='%s'"%(bd,cambiar,editar))
            ztux.close()
            print 'Contacto Actualizado...'
            raw_input("> Press Enter...")
            run()
        elif opc=='+':
            run()
        else:
            print 'Opcion Incorrecta...'
            run()
            
    except:
        print '[*]Error al conectar a la base de Datos...\n'
        raw_input("> Press Enter...")
        run()

def borrar(server,user,passwd,bd):
    try:
        db = MySQLdb.connect(server,user,passwd,bd)
        borrar = raw_input('[+]Nombre del contacto: ')
        ztux = db.cursor()
        ztux.execute("delete from %s where nombre='%s'"%(bd,borrar))
        ztux.close()
        print '[+]Contacto borrado con exito...'
        raw_input("> Press Enter...")
        run()
    except:
        print '[*]Error al conectar a la base de Datos...\n'       
 
def run():
    os.system('clear') #Cambiar "clear" por "cls" si Usas Windows
    print '-------------------------'
    print '    Agenda by [Z]tuX     '
    print 'http://ztux.blogspot.com/'
    print '   ztux.ztux@gmail.com   '
    print '-------------------------'
    print '''[1] Agregar contacto 
[2] Ver contactos    
[3] Buscar Contacto  
[4] Editar Contacto  
[5] Borrar contacto  
[0] Salir            
''' #CONFIGURAR AQUI#
    server='localhost' #Servidor MySQL
    user='root'        #Usuario MySQL
    passwd='chucho'    #Passwd MySQL
    bd='contactos'     #Base de Datos
    #################
    opc = raw_input('> ')
    if opc =='1':
        agregar(server,user,passwd,bd)
    elif opc =='2':
        ver(server,user,passwd,bd)
    elif opc =='3':
        buscar(server,user,passwd,bd)
    elif opc=='4':
        editar(server,user,passwd,bd)
    elif opc=='5':
        borrar(server,user,passwd,bd)
    elif opc=='0':
        return 0
    else:
        print '[*]Opcion Incorrecta...'
        run()
run()

Eso es todo, probado con Python 2.7...Salud[OS]