I had the same issue on my website http://loctim.com because I wanted
the slug like this %category%/%state%/%city%
I had 404 pages in changing functions.php and today it is the gallery which was crazy. So i worked all the night and I have found that I had forgotten this part of code :
function add_category_endpoint_tag() {
add_rewrite_tag( '%category%', '([^/]*)' );
}
add_action( 'init', 'add_category_endpoint_tag' );
Please try to put that previous code just before (yours) this one :
function add_region_endpoint_tag() {
add_rewrite_tag( '%region%', '([^/]*)' );
}
add_action( 'init', 'add_region_endpoint_tag' );
I hope that will help you. I have more code about that slug if you are interested in, for example how to automatically replace %state% by the %country% if the %state% = %city% (some cities are in that case as in usa or Portugal)