My instinct suggests that a viral video site would be better served by tagging than categorization as a navigation metaphor.
Categories are buckets into which items are placed.
Tags are attributes which are assigned to an item.
It is implied that an item belongs in one category while that same item might have multiple tags.
If you give your authenticated visitors the ability to recommend predefined tags for the most recently added videos and to suggest new tags when the predefined list is inadequate, you could quickly find your videos annotated with descriptive tags which might make the categorization process significantly easier (and/or unnecessary).
You will want to put some fuzzy logic into the relationship between a video and a tag. How many visitors recommended the tag? How mainstream has each recommending visitor's tagging of previous videos been? Each vote for a given tag and video pairing should add a fractional weight to the validity of that pairing. When a particular threshold is met in that weighting, the tag can be automatically added to the video's public interface.
The whole system can be automated and community policed much like the SE forums. Visitors with strong site reputations can be empowered to review the video-tag pairings and flag those which seem inappropriate. You may discover that enough information is gathered by the contributing membership to provide for a dynamic and intuitive public interface, saving you the task of creating and maintaining a manual category tree.