In Office 365, you may have encountered this strange error where it throws an error "Sorry you're not set up to follow" when you try to Follow a Document or Site. There might be more information about the above error message such as "Unfortunately, it looks like your account hasnt't been set up to follow documents or sites."
The way to solve this issue is to login as Office 365 Global Administrator account to SharePoint Online Administration and navigate to the following - User Profiles -> People -> Manage User
Permissions and enable the following checkboxes for the group "Everyone except external users"
Wait for 5-10 mins and VOILA! your users will now be able to follow sites and documents.
