I think there are 2 different data for a user:
Meta data: contains user name, lud16 address etc
Contact list: contains relays and follows.

So if you update your relay list when you don't have your follows synced, this might cause the problem.