The configuration example was only partial. First of all, you need to put the rewrite rules under server { } section of the configuration file. For example,

http {
  ...
  ...
  server {
    server_name www.my-drupal-site.com;  
    if (!-e $request_filename) {
      rewrite ^/(.*)$ /index.php?q=$1 last;
    }
  }
}

I am running Drupal 5 on Nginx on my devel box and it has no issue doing clean URL.