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.