Pagination on my wordpress tags not working, redirection applied?

Question

I've got a WordPress site that works fine except for one thing. When I search for certain tag the first page of results appear, but when I try to navigate to the second (third, fourth...) page of results I get a 404 page.

This is strange because the rest of the pagination system works (searches, categories, etc), so I don't know where to look.

My WordPress site is under Nginx, and when I try to access for example

http://www.mysite.com/tag/google/page/2

or

http://www.mysite.com/tag/google/page/2/ (with the final slash)

I get these access log lines

95.18.98.212 - - [24/Oct/2011:13:50:21 +0200] "GET /tag/google/page/2/ HTTP/1.1" 301 5 "-" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/535.2 (KHTML, like Gecko) Chrome/15.0.874.102 Safari/535.2"
95.18.98.212 - - [24/Oct/2011:13:50:26 +0200] "GET /tag/ HTTP/1.1" 404 11550 "-" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/535.2 (KHTML, like Gecko) Chrome/15.0.874.102 Safari/535.2"

Seems to be a redirection to /tag/ (www.mysite.com/tag/), but this doesn't work and doesn't load the proper result page. My Nginx config file for this site is as follows:

server {
              listen   80;
#             access_log  /var/www/mysite/log/access.log;
#             error_log      /var/www/mysite/log/error.log info;
              server_name     www.mysite.com;
              root /var/www/mysite/;

              location / {
              index index.php;
              try_files $uri $uri/ /index.php?q=$uri&$args;
              # if the requested file exists, return it immediately
                if (-f $request_filename) {
                break;
              }

              # all other requests go to WordPress
              if (!-e $request_filename) {                                                                             
                rewrite . /index.php last;
                }
      }

## Images and static content is treated different
    location ~* ^.+.(jpe?g|gif|png|ico|css|zip|tgz|gz|rar|bz2|doc|xls|exe|pdf|ppt|txt|tar|mid|midi|wav|bmp|rtf|js|swf|\
avi|mp3)$ {
      access_log        off;
      expires           30d;
      root /var/www/mysite/;
        }


## Parse all .php file in the /var/www directory
    location ~ .php$ {
        fastcgi_split_path_info ^(.+\.php)(.*)$;
        fastcgi_pass   backend;
        fastcgi_index  index.php;
        fastcgi_param  SCRIPT_FILENAME  /var/www/mysite/$fastcgi_script_name;
        include fastcgi_params;
        fastcgi_param  QUERY_STRING     $query_string;
        fastcgi_param  REQUEST_METHOD   $request_method;
        fastcgi_param  CONTENT_TYPE     $content_type;
        fastcgi_param  CONTENT_LENGTH   $content_length;
        fastcgi_intercept_errors        on;
        fastcgi_ignore_client_abort     on;
        fastcgi_read_timeout 360;

    }


    ## Disable viewing .htaccess & .htpassword
    location ~ /\.ht {
        deny  all;
    }
}


upstream backend {
              server 127.0.0.1:9000;

}

Any ideas?