Search doesn't find nodes (when searching based on category names)

I've got a site with video clips organized by location. Here's an example of my structure:

Location (contianer)
----> United States (category)
------->California (category)
---------->Los Angeles (category)
-------------->video clips pertaining to Los Angeles (nodes)

So the problem I have is that if I do a drupal search for California, Los Angeles or United States, I only get the category listing (the category as a node) I don't see any of the video clips (nodes) associated with those categories.

It seems like the category information is not being applied to the node in a searchable way (i.e. the way taxonomy works).

The only workaround I've found is if I turn off the Taxonomy wrapper and re-enter all the above locations as keywords. Its a workable solution, but seems like it shouldn't be necessary.

Am I doing something wrong? Does anyone else have this problem.