How do I get a new directory to show up with 'cvs update'?

Howdy folks.  Scenario: Two developers and/or just me with multiple 
sandboxes.  If a new subdirectory is added from one sandbox and committed 
properly, a 'cvs co' will properly create the subdirectory but 'cvs update' 
in the existing sandboxes does not add the new directory.  I can't find 
anything in the documentation on how to do this.  I know I could create a 
new sandbox and overlay directories or abandon the existing sandbox and 
create a new one but this seems wrong.  Surely there is a documented way to 
do it.  What am I missing?

--
Harvey