You need to flush and regenerate your permalinks everytime you modify/add/remove custom post types or taxonomies.
Going to the permalinks page and saving should be enough
( Also your custom post type code should be in a plugin, not the theme, else the user is stuck using that theme forever )