I strongly suspect the problem may be related to not having put your pages into a public static resource made public in the form of a zip file that's less than 1MB in size of the structure as specified in the document I've quoted from below.
From the Force.com Sites Implementation Guide:
Assigning Force.com Site Error Pages
To set the error pages for your site:
From Setup, click Develop > Sites.
Click the name of the site you want to modify.
Click Page Assignment on the Error Pages related list.
Using the lookup fields, assign a Visualforce page or static resource for each of the standard error conditions listed:
• Authorization Required Page—The page users see when trying to access
pages for which they do not have authorization.
• Limit Exceeded
Page—The page users see when your site has exceeded its bandwidth
limits.
• Maintenance Page—The page users see when your site is down
for maintenance.
• Service Not Available Page—The page users see when
Salesforce servers are unavailable. This custom page is rendered from
a static resource that you choose. The static resource is uploaded to
the cache server when assigned as the Service Not Available page, and
when updated after assignment. The custom page is shown for HTTP
requests only; caching is not used for HTTPS. Not available for
Developer Edition or sandbox organizations.
If you haven't set a custom page for a site that uses a site prefix,
the custom page for the root site is used when servers are
unavailable. For example, if http://mycompany.force.com/sales doesn't
have a custom page, but http://mycompany.force.com does, that custom
page is used. Otherwise, the Maintenance page is shown by default
Note: The static resource:
◊ Must be a public zip file 1 MB or smaller.
◊ Must contain a page named maintenance.html at the root
level of the zip file. Other resources in the zip file, such as
images or CSS files, can follow any directory structure.
◊ Must
contain only files that have file extensions.
• Page Not Found Page—The page users see when trying to access a page
that cannot be found. You can use the action attribute on an
component to redirect the Page Not Found error page. Using
this kind of redirect on any other error pages will redirect users to
the Maintenance page.**
• Generic Error Page—The page users see when
encountering generic exceptions.
Note: When using static resources in a custom error page—such as a large image file or a large CSS file contained in a static resource
.zip file—each individual resource must be no larger than 50KB.
Otherwise, a 404 not found error is returned for that resource.
(5. Click Save.
(6. On the Site Details page, click Preview to view the associated page as it would appear in a browser.
Tip: Add the component right before the closing tag in your custom Visualforce error pages to
view detailed site error messages in administrator preview mode.