Hola, que tal!!
Bien el dia de hoy hice este code, una "Agenda" en Python, usando una base de datos previamente creada, la base de datos en este caso se llama "contactos" y esta base de datos tiene una tabla que contiene campos para "Nombre" y "Teléfono"...

Bien dejare el code del "Programa", es importante que para que funcione tengan instalado MySQL en su ordenador, Python 2.x [Obvio] , tener la libreria de MySQL para python, que en una distro GNU/Linux Ubuntu se instalaría así:

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" y "telefono"... Mas o menos asi xD:

create database contactos;
use contactos;
create table contactos(nombre varchar(50),pass varchar(25));

Eso seria la base de datos para poder hacer funcionar nuestro "Programa"...
Ahora si Aquí el code...

#!/usr/bin/Python

import MySQLdb

def agregar(server,user,passwd,bd):
    db = MySQLdb.connect(server,user,passwd,bd)
    cursor = db.cursor()
    name = raw_input('[+]Nombre: ')
    telefono = raw_input('[+]Telefono: ')
    cursor.execute("insert into contactos (nombre,telefono) values ('%s','%s')"%(name,telefono))
    print 'Datos agregados correctamente...'
    cursor.fetchall()
    cursor.close()
    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:
            print i
        ztux.close()
        run()
    except:
        print '[*]Error al conectarse a la base de Datos...'
        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()
        print a
        ztux.close()
        run()
    except:
        print '[*]Error al conectarse a la base de Datos...'
        run()
        
def editar(server,user,passwd,bd):
    try:
        db = MySQLdb.connect(server,user,passwd,bd)
        print '[1]Nombre\n[2]Telefono'
        opc =raw_input('Que desas editar: ')
        if opc=='1':
            editar = raw_input('[+]Nombre del contacto a editar: ')
            cambiar = raw_input('[+]Escribe el nombre del nuevo contacto: ')
            ztux = db.cursor()
            ztux.execute("update %s set nombre='%s' where nombre='%s'"%(bd,cambiar,editar))
            ztux.close()
            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...'
            run()
        else:
            print 'Opcion Incorrecta...'
            run()
            
    except:
        print '[*]Error al conectar a la base de Datos...'
        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...'
        run()
    except:
        print '[*]Error al conectar a la base de Datos...'        
 
def run():
    print '-------------------------'
    print '    Agenda | [Z]tuX v1.0 '
    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='toor'      #Passwd MySQL
    bd='contactos'     #Nombre de 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!Alguna Duda?
Comenta, si vas a modificar el Code, coloca algunos créditos por ahí Vale? xD
Probado en Ubuntu 11.04 y Python 2.7
[Z]tuX!!