This is an 11 month old question, but this appears to be an issue still. I'm having the same exact problem.
I've tried deactivating/reactivating the plugin. I've tried numerous other slug names. I've even manually changed the value of "skt_flush_rewrite_rules" to "1" in my database to try and force this to work: nothing.
I can still get to individual pages using a query string (http://hostname/?sk_testimonials=testimonial-slug-name-here). But if I try going to the pretty link version (http://hostname/testimonials/testimonial-slug-name-here) or the index page (http://hostname/testimonials/), I get a 404 Page Not Found error.
For the time being, I'm having to create a temporary rewrite rule in my .htaccess file:
# BEGIN Manual Rewrite Rules
RewriteRule ^testimonials/(.*)$ index.php?sk_testimonials=$1 [L,QSA]
RewriteRule ^testimonials$ index.php?post_type=sk_testimonials [L,QSA]
# END Manual Rewrite Rules