I made a clean 1.16.0 install using an sqlite backend, then created a page that contained only:
The "Category: Tests" link appeared correctly at the bottom of the page, but the Category:Tests page itself says only "This category currently contains no pages or media."
A repeat of the same test on a MySQL installation behaves correctly.
From my quick, ignorant poking at the DB, it looks ok -- both the categories and categorylinks tables have sensible-looking rows in them -- but I really have no experience here.
Interestingly, sub-categories do work correctly -- which makes me wonder if it's a side-effect of whatever was done to fix bug 16966?