Today I’ll talk about an existing bug on SharePoint Online. It may happen that you cannot add photos to your profile. When trying to upload a photo, an error message appears: “error – You don’t have sufficient permissions. To get permissions, contact your administrator”. And even with the administrator account.
After searching a while, I came across this topic: http://community.office365.com/en-us/forums/156/p/192193/585053.aspx
Apparently this is a known problem, to solve it , post a message on this topic, a Microsoft support will contact you to ask you for information about your tenant in order to apply a hotfix.
This solved the problem for me!
Hope this helps!