The fact that you are using Publishing features shouldn't have an effect on permissions. Publishing (for the most part) really has more of an effect on how edits are handled - i.e. immediately deployed or checked in and published at a later point. That's oversimplifying it - but back to your question.
Most likely - what is happening is that you have not given the user permission to the library where the template is that they need access to in order to create the page. I'm 99% sure that is what is happening here. Makes sense - they have the rights to the site - and permissions to edit the pages that exist - but creating a page requires them to access a new file - in a different library. If they don't have permissions to that template library - you get the access denied error.
When your user tries to create a page, they get an access denied error page correct? Copy the URL of that page, and examine it closely. It should reveal the location of the template folder they are trying to access but don't have permissions for. Read-only access to that template library should get your user the access they need.
One other recommendation - check out the access checker web part in Codeplex. http://accesschecker.codeplex.com/. This web part is loaded as a solution and allows you to display a hierarchical list of the sites that a specific user has permissions to. VERY helpful in confirming that you have given the permissions you thought you had.
Finally - in terms of permissions best practices - I think you are doing fine. You've gotten a little frustrated because you took a different path on a site (i.e. publishing) and it's behaving differently. But nothing is wrong. I've been there:) You really have two options w/ SP permissions - SP based groups (visitors, members, owners etc) or pulling in AD groups. Either way, you'll be making the same decision regarding unique or inherited permissions. You either use the same permissions as the parent site - or use unique permissions. HTH