New categories not showing up

When I create a new media category in ACP it's not showing up in gallery as a new category to choose from.

On the other hand, in ACP I have nine media categories but when I go to gallery it's showing twenty five categories. I don't understand the discrepancy here, although it's possible I'm missing something not clear to me.

Anyone?

Hi Tim Düsterhus

Thanks for your reply. This wasn't so easy to find if I'm honest, because I thought categories covered everything.

All sorted now, so, many thanks.