Sorry, only tenant administrators can add or give access to this app

So, I just created my SharePoint Hosted App. Nothing fancy, just the default SharePoint Hosted App project template using Visual Studio and some minor plumbing to retrieve the user profile information using the JSOM.
After deploying the App, I was continuously getting error following error.

Access denied. You do not have permission to perform this action or access this resource.

I started debugging and found that this error occurs when I access the user profile store. Strange! Because, I had already specified the Read permissions for User Profiles in App using the AppMenifest.xml

UserProfileDemo_Permissions

And it turns out to be that after deploying the App, you need to say that you trust this App to access the resources (in this case, user profile store). I went ahead and guess what, another shocker in the form of the message below and for some reason I am not allowed to trust the App I just built.

Sorry, only tenant administrators can add or give access to this app

UserProfileDemo

But hey, this is my development environment. I have the Farm Administrator rights as well as the Local Administrator rights on the machine.

Resolution

After looking around on Google if there are other people having the same issue, I found this blog post from Chris Weldon. He suggested to add user explicitly to the Farm Administrator group. But it turned out that this was not enough to solve the issue I was facing.
Finally, what worked me was something similar. I added my user account explicitly to the Local Administrator group on my machine, reset the IIS and yes it works. 