Come pensavo, non hai indicato la lunghezza del record nella Open ...
Dato che non l'hai specificato, per default, viene assunto un valore di 128 byte ... e fino a che il record ha avuto una lunghezza minore, tutto e' andato bene.

Dopo che il tuo record si e' ingrandito oltre questa misura, hai avuto il problema ...

Correggi impostando nella Open la lunghezza del record (che e' quella della variabile di tipo Contatto che hai chiamato C).
Quindi
codice:
Open App.Path + "\Rubrica.rbc" For Random As #1 Len = Len(C)
Ovviamente dovrai cancellare il vecchio file dei dati perche' incompatibile con quello nuovo.

Il consiglio finale e' di dare un'occhiata (ovvero studiare ...) la sintassi di ogni istruzione che usi (nell'help o su internet) perche' altrimenti le usi "al buio" e puoi avere parecchi problemi ...