This is the nginx directive to make the rewrite work. This example works if your store is installed in your webroot. "mysite.com"
Code:
location / {
    try_files $uri /$uri /index.php$is_args$args;
}
If you need "mysite.com/store":
Code:
location /store {
    try_files $uri /$uri /index.php$is_args$args;
}
It does not appear that this is dependent on relative position in your vhost file like nginx restrictions.
Code:
/etc/nginx/sites-available/mysite.vhost