If a user doesn't have permissions to view any particular namespace, a no permission error will occur on the Special page, if the Special page attempts to list articles from the namespace.
If no namespace was specified, it will automatically use the Default namespace. In your case, you had lost permissions for the Default namespace, so you lost permissions for the default Special action.
This is an issue with Special pages overall, as long as they search by namespace, and would require a rewrite to practically every one. This is flagged for the 3.x series.