Problem:
I created new page layout in the VS solution and deployed the solution. The new page layout is provisioned in the gallery. It is approved. I cannot see it in the UI as available page layout.

Solution worked for me is to check in the sites “/_Layouts/AreaTemplateSettings.aspx” for “Pages in this site can use any pagelayouts”
Go to Site Settings, under “look and feel” click on “Page layouts and site templates”. Make sure the “pages in this site can use any pagelayouts” is selected.