We are encountering an issue that seems to have also been encountered by the user who asked https://community.playfab.com/questions/144901/playfab-login-issue-with-steam-first-time-users.html
Similarly, no new Steam users across multiple of our titles have been able to login to PlayFab since April 18th, with the same error message ("Steam API rejected request as unauthorized due to invalid title Application ID or Publisher Key").