acordes.py

import random

notas = ['C', 'D', 'E', 'F', 'G', 'A', 'B']

while True:
    nota = random.randint(0, len(notas) - 1)

    if nota == (len(notas) - 1):
        nota = 0

    print "\nA nota eh: %s" % notas[nota]

    anterior = raw_input('Qual a nota anterior? ')
    anterior = anterior.upper()

    if anterior == notas[nota - 1]:
        print "Correto"
    else:
        print "Incorreto, o correto eh: %s" % notas[nota - 1]

    proximo = raw_input('Qual a proxima nota? ')
    proximo = proximo.upper()

    if proximo == notas[nota + 1]:
        print "Correto"
    else:
        print "Incorreto, o correto eh: %s" % notas[nota + 1]
    

acordes2.py

import random

class Nota(object):
    nota = None

    def anterior(self):
        raise NotImplementedError('Voce deve implementar nas classes filhas')

    def proxima(self):
        raise NotImplementedError('Voce deve implementar nas classes filhas')

    def __unicode__(self):
        return self.nota

    def __eq__(self, outra):
        if isinstance(outra, Nota):
            return self.nota == outra

        if isinstance(outra, str):
            return self.nota == outra.upper()


class C(Nota):
    nota = 'C'

    def anterior(self):
        return B()

    def proxima(self):
        return D()


class D(Nota):
    nota = 'D'

    def anterior(self):
        return C()

    def proxima(self):
        return E()


class E(Nota):
    nota = 'E'

    def anterior(self):
        return D()

    def proxima(self):
        return F()


class F(Nota):
    nota = 'F'

    def anterior(self):
        return E()

    def proxima(self):
        return G()


class G(Nota):
    nota = 'G'

    def anterior(self):
        return F()

    def proxima(self):
        return A()


class A(Nota):
    nota = 'A'

    def anterior(self):
        return G()

    def proxima(self):
        return B()


class B(Nota):
    nota = 'B'

    def anterior(self):
        return A()

    def proxima(self):
        return C()


notas = [C(), D(), E(), F(), G(), A(), B()]

while True:
    nota = random.choice(notas)

    print "\nA nota eh: %s" % unicode(nota)

    anterior = raw_input('Qual a nota anterior? ')

    if anterior == nota.anterior():
        print "Correto"
    else:
        print "Incorreto, o correto eh: %s" % unicode(nota.anterior())

    proximo = raw_input('Qual a proxima nota? ')

    if proximo == nota.proxima():
        print "Correto"
    else:
        print "Incorreto, o correto eh: %s" % unicode(nota.proxima())
    

Massa @dimiro1, muito legal :)

Uma nova versão mais Orientada a objetos