I am having the same issue using WP 3.0.1 and RS 1.3.28.

When I add a new category, it is restricted by default (per my settings).  But when I assign a user to a role, it appears as assigned in the "category assigned" admin page of RS, but when logged in as the user, the category is not present.

Q: What roles do you have restricted and assigned?

A:

Post Reader: Unrestricted by default
Private Post Reader: Restricted by default
Post Contributor: Restricted by default
Post Author: Restricted by default
Post Editor: Restricted by default
Category Manager: Restricted by default
Category Assigner: Unrestricted by default 

Q: By "not present", do you mean the category checkbox is not available for selection in the post edit form?

A: The new category appears on /wp-admin/admin.php?page=rs-category-restrictions_t but it is not showing up when I use <?php wp_list_categories('name=quick_post_cat'); ?> in header.php (all the older categories do appear per role just fine).

Q:  If so, is that for a new or existing post?

A: New post and when creating navigation for user-allowed cats in header.php.

Q: If existing, what is the post status (visibility) and are any restrictions set directly on the post?

A: I can login as admin and go to Posts > Categories and see the newly created category just fine.  If I edit the new category, the cat restrictions and cat roles appear correctly.  I have assigned a user to "Post Contributor" role.  I have tried different users as well - no difference.

NOTE: I bounced the RS plugin by deactivating and reactivating and didn't get any result.  Also, I was running exec php plugin and thought it could be causing conflict - so I removed and deleted that plugin and tested: no change.

Kevin said:

It appears that your new category is not included in the list because it has no posts! Try this:

wp_list_categories('name=quick_post_cat&hide_empty=0');

Be aware that setting the name to quick_post_cat causes the categories to be filtered based on the user's editing capabilities. If you want it filtered based on reading capabilities, name it anything else.

Whoa!  I've been so perplexed, I forgot to see the obvious!  I did a nice face plant and have the red hand marks to prove it now.

The fix works.   Thank you!

In my navigation, I'm only using quick_post_cat for logged-in users.  All users are able to post, so I'll see about making some changes so that editing capabilities don't slip through.