On a recent upgrade from Drupal (information at http://www.drupal.org) v4.6.x to v5.1, I discovered that many of my "protected" pages were again publicly accessible. Since I'd already done the conversion on my production drupal instance, this was of some concern to me, but due to time constraints there was little I could do about it. Since my time was at a premium, I wasn't able to look at it until Thursday night (July 26th), after doing the conversion the prior weekend. That's when I discovered that the fix was actually fairly simple to implement.
The first thing I had to do was truncate the nodaccess table. PhpMyAdmin (which I have installed) does this easily, but you can also use native SQL to do the same thing. (The MYSQL command is: TRUNCATE TABLE nodeaccess;)
After doing that, I just had to log back into my site as a user with Administrative rights (full rights) and to Administrator -> User Management -> Node Access (i.e., /admin/user/nodeaccess URL) I was able to re-save my grants. This populated the nodeaccess table and my "protected" pages were once again unavailable to anonymous users.
Again, it was a relatlvely simple fix, but required some free time to fully research.