How to authorize users to use SAML2 bearer oauth flow?

I am new in the forum as a signed up user but have been lurking for a while. I have the following setup:

• a connected app with a certificate associated
• associated the system admin profile to the app
• created a permission set and added my user and a few other to it and then added the permission set to the connected app.

My goal is to leverage SAML2 bearer token to obtain an access token and make calls to force.com to retrieve data to display in an external Saas system.

When I try posting the assertion following the instructions here:

https://developer.salesforce.com/page/Digging_Deeper_into_OAuth_2.0_on_Force.com#Obtaining_an_Access_Token_using_a_SAML_Bearer_Assertion

The response I am getting right now is:

400 (Bad Request) {"error_description":"user hasn't approved this consumer","error":"invalid_grant"}

In the user's login history I see a corresponding error stating:

Failed: Not approved

Any suggestions on what I can do next to debug this issue to have the user authorize the app? Also, is the user required to go through the Oauth dance at least once before this works? My goal was to avoid users going through the Oauth dance and have SAML2 bearer token to handle the authorization.

Thanks in advance.

Attribution to: user8242
This content is remixed from stackoverflow or stackexchange. Please visit https://salesforce.stackexchange.com/questions/34546