Special:NewPages checks the existence of a page by id, but refers to it by name; when the page is renamed, the two can become out of synch.

Steps to reproduce:

1. create page Foo
2. rename it to Bar

Expected result: there are two new records on Special:NewPages, Foo and Bar. When you delete Foo, the record for Foo disappears (and vice versa).
Actual result: there is one new record, for Foo. Deleting Foo does not affect it, but it disappears when you delete Bar.

1. create page Foo
2. rename it to Bar, suppressing redirect creation

Expected result: there is a new record on Special:NewPages, Bar. It disappears when Bar is deleted.
Actual result: the record is called Foo. (It does disappear when Bar is deleted.)

Bugs that are special cases of this: bug 16705 (T18705), bug 17463 (T19463), bug 17536 (T19536).

Two real-world problems caused by the bug:

You can create pages under the radar of the new page patrol by immediately renaming them and overwriting the redirect with another article.

On wikis with FlagRev enabled, if an unreviewed page is moved into a non-reviewed namespace (to a user subpage, for example), Special:NewPages will list it when queried for new pages in main namespace, and put "not-patrolled" class on (which will probably make it stand out and be an annoyance for patrollers).