Permissions are multi-faceted. In order to create a page you need
- Permission to the page (check)
- Permission to create a page in that location (check)
- Permission to use the tools that are needed to create a page in general (UI Personalization)
I believe #3 is where you may be having the problems, go to the Roles module, select your role, then click on "UI personalization" and check out the "CMS - Administration - Content Management - Pages - New" section and see what you have there!