You need to add the rewrite rules yourself. This code should work:
function prefix_this_add_rewrite_rules() {
// Add day archive (and pagination)
add_rewrite_rule( '/([0-9]{4})/([0-9]{2})/([0-9]{2})/page/?([0-9]{1,})/?', 'index.php?post_type=cats&year=$matches[1]&monthnum=$matches[2]&day=$matches[3]&paged=$matches[4]', 'top' );
add_rewrite_rule( 'cats/([0-9]{4})/([0-9]{2})/([0-9]{2})/?', 'index.php?post_type=cats&year=$matches[1]&monthnum=$matches[2]&day=$matches[3]', 'top' );
// Add month archive (and pagination)
add_rewrite_rule( 'cats/([0-9]{4})/([0-9]{2})/page/?([0-9]{1,})/?','index.php?post_type=cats&year=$matches[1]&monthnum=$matches[2]&paged=$matches[3]', 'top' );
add_rewrite_rule( 'cats/([0-9]{4})/([0-9]{2})/?', 'index.php?post_type=cats&year=$matches[1]&monthnum=$matches[2]', 'top' );
// Add year archive (and pagination)
add_rewrite_rule( 'cats/([0-9]{4})/page/?([0-9]{1,})/?', 'index.php?post_type=cats&year=$matches[1]&paged=$matches[2]', 'top' );
add_rewrite_rule( 'cats/([0-9]{4})/?', 'index.php?post_type=cats&year=$matches[1]', 'top' );
}
If you do this in a plugin, you need to call this function upon activation (via register_activation_hook()), and then flush the rewrite rules. In a Theme, hook into after_switch_theme.
You can use this plugin to help you with the debugging effort: http://wordpress.org/extend/plugins/rewrite-rules-inspector/