Hast Du dabei den Bezirk gewechselt?

Im Normalfall:
Mit dem Mietvertrag o. Ä., Pass, Residencia (alles mit Kopie!) zum Rathaus und umschreiben lassen. Die Daten haben sie eh alle im Computer. Geht ratz-fatz.
Die Residencia muss man meines Wissens nicht ändern lassen, solltest Du noch das A4 Blatt haben ist es aber eine gute Möglichkeit sie gegen die Karte eintauschen zu können.
Für Global ist Kuehnetec der bessere Informant.
Konsulat kannst Du informieren, braucht man aber nicht. Wozu auch?
Hast Du hier einen PKW, musst Du zum Trafico und die Anschrift ändern lassen. Pass, Residencia, Empadronamiento, Fahrzeugpapiere (alles in Kopie!) mitnehmen. Sicherheitshalber auch den KFZ Steuerbescheid einstecken bzw. die Zahlungsbestätigung.