A mi me pasó, parece ser que Nintendo borra los códigos amigos "antiguos".
Haz esto:
Mete ESE juego en OTRA CONSOLA. Y luego te vas a hablar con el perro para que te dé un nuevo código amigo para ESA CONSOLA.
Mete EL juego en TU consola y le das a k ponga otro vez el código amigo.
FIN.
Nintendo limpia de vez en cuando lo códigos amigos, a mi me pasó con mi cartucho original a unos de los 4 habitantes.