I'm not sure the problem is really fixed: what I suggested makes the post load in a different way, so it doesn't trigger what you were seeing before, but what you were seeing isn't supposed to happen, so whatever it is that caused the problem must still be lurking somewhere... If you wish, you can set the number of posts per page to less than 10 in Settings > Reading, so I can see what happens when you move from page 1 to page 2 of your posts.
"Photo Gallery" isn't a category like the rest of the items of that dropown, it's a static page. Is that ok or should it really be a category? If you mean you want some text right above the images when you view this page:
then no, there's no reason why you wouldn't be able to add it (other than a mistake of yours or a temporary glitch or a browser issue). You just go to Pages > All Pages, click the title of the page to edit it, make sure the cursor is at the left of the rectangle that represents the gallery, press enter to make room for the text, type text, click Update.
Perhaps easier if you switch the editor to Text (=code): place the cursor before the opening bracket of the gallery shortcode, press enter once or twice, etc.