I was able to resolve this (for external users on a Salesforce community who log in via SSO but do not have access) by creating a custom page in my community that has an embedded VF page, and then editing the site's single sign on settings to point to this new community page where my custom error message lives as follows:
1) Go to Single Sign-On Settings and click on the single sign on setting you would like to edit.
2) Once you are in the SSO settings, find the "Custom Error URL" field, and enter the url of the community page that has the embedded VF page with your custom error message on it.
3) And that is it!