I was able to reproduce this and have reported this to the engineering team. I will let you know as soon as I have a response from them.
That said, I have seen this happen in the past in my own tenant and sometimes the change can take 2-3 days to reflect.
It sounds like you area already doing the right things and like I said I am seeing the same issue, but some steps to try:
1) Login to Azure Portal using a user whose picture needs to be changed
2) Switch the directory of the user to the default directory through Azure Portal
3) Go to Azure Active Directory, All Users
4) Select the user, in the profile change the photo
5) Log out and log back in
6) Wait 2-3 days if the photos still have not reflected.