In case this can be helpful to anyone else, here is the solution:
Despite Slack documentation showing the userInfo call as a GET method, calling a POST method finally got this to work. Here are screenshots of my API calls for getting the access token and collecting the User Info:
Note that the Content-Type in both cases is: application/x-www-form-urlencoded
Also, body type for both is Form-data (not JSON!)