I was speaking (or rather IM'ing) with Ben Collins a while back and he came across an interesting problem that I wanted to document for the sake of posterity.  If you have a SharePoint user who has permissions to create a page in a page library, but that user is having security issues trying to actually make a page, then it the security issue may be related to their access rights on the master page gallery.  Users who create pages must have at least restricted read access to the master page gallery for page creation to succeed.

That is one of the joys of working in SharePoint. if something doesn't show up there is usually a good but obscure reason for it, but SharePoint certainly won't tell you outright why it is.  All I have to say is that I'm glad he ran into that issue and not me.