Fixed my problem!
It seems that updating messed up with the accounts that had access to my contacts.
For me it was "Facebook contact sync" which syncs facebook contact's profile picture with my phone contacts.
After I uninstalled the app the problem was fixed.
Better yet, I reinstalled it again and everything works great.
I recommend to uninstall every app that uses contacts and delete every account that sync them, then reinstall and sign in accounts again