The key thing is that their must be contact data in the directory for each user before they will be able to use the service. This means you will need to either enter the contact data manually, sync it in, or provide it programmatically in some fashion as I explain in the video. In the topic I provided a link to in my last comment there is this blurb:
"In order for users to take advantage of self-service password reset functionality, their cloud user accounts must be updated with the correct contact data to ensure that they can pass through the appropriate number of password reset challenges defined by their administrator."
Basically, this means that if you have enabled the service for all users in your cloud directory and only 5 users actually have their contact data specified in your cloud directory, only those 5 will be able to use the self-service password reset capabilities.
There's a user registration portal that you can send to your users so they can get that data in there and that option as well as other options are explained in the topic so hopefully it helps you out.