Creating a Video Site

My friend and I are trying to create a video website with WordPress as the CMS. We have WP installed but are having trouble finding some good free themes, along with plugins that will support videos.

The main goal is to allow registered users to upload their own videos (not just link from YouTube or Vimeo) and assign them specific categories. We looked at the Kalutra plugin, but unfortunately we don’t want to pay for it, we don’t have a lot of money.

Are there any ideas to help us with getting this started?