Is there a way to use regular categories with custom post types?

No problem, the categories and tags are also registered as taxonomies that you can pass to the taxonomies argument when you call register_post_type(). Categories are category and tags are post_tag. You can also do this later with register_taxonomy_for_object_type():

add_action( 'init', 'wpse6098_init', 100 ); // 100 so the post type has been registered
function wpse6098_init()
{
    register_taxonomy_for_object_type( 'category', 'your_custom_post_type' );
}