Hey everyone! So I went ahead and emailed them and guess what? They sent me my new registration papers in just a few days. Go
Kreuzberg!! All they needed to know was:
-full name
-old address
-new address
-what floor the new apt. is on
-the manager / company you are renting from
-zipcode
Here's the email address in case anyone else wants to give it a shot: poststelle@labo.verwalt-berlin.de