I will try other sitemap plugin if 404 error occurs again.
Somehow, my 404 Error problem was fixed in version 4.0.6.
I’m using version 4.0.5 on WP3.9.1/nginx and have set rewrite rules as namhuy posted, however, still having the 404 error.
When I retrieve the sitemap from a browser, it is surely displayed, but the HTTP status code is 404.
In my environment, HTTP status code is somehow 404 on line 1615 of sitemap-core.php. So, I have patched the plugin:
*** sitemap-core.php.orig 2014-06-01 08:41:03.875005874 +0900
--- sitemap-core.php 2014-06-01 08:40:33.483004966 +0900
***************
*** 1612,1617 ****
--- 1612,1618 ----
if($html) {
ob_start();
} else {
+ header('HTTP/1.1 200'); // PiuLento
header('Content-Type: text/xml; charset=utf-8');
}