Confused about the way this .htaccess rule is supposed to work

I have this in my .htaccess

RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d    
RewriteRule ^users/([^/]+)/?$ users.php?user=$1 [NC,L]

in my php I have

header("Location: /users/" . $_SESSION['user']);

it loads this into the browser

foo.bar/users/s2xi

which gives me a 404 Not Found error, I can understand up to the part where the directory users doesn't exist, but isn't my RewriteRule supposed to take care of that?

Edit: My complete .htaccess

Options +FollowSymlinks
RewriteEngine On
RewriteBase /

RewriteCond %{HTTP_HOST} ^foo\.bar$
RewriteRule (.*) http://www.foo.bar/$1 [R=301,L]

RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d

#RewriteRule ^([a-zA-Z0-9_\s-]+)/([a-zA-Z0-9_\s-]+)(/)?$ users.php?type=$1&user=$2 [NC,R]
#RewriteRule ^users/?$ users.php [L]
RewriteRule ^([^/]+)/?$ profile.php?user=$1 [NC,L]
#RewriteRule ^users/([^/]+)/?$ users.php?user=$1 [NC,L]
#RewriteRule ^(admin)/(.+)/?$ users.php?user=$1 [NC,L]
RewriteRule ^admin/([^/]+)$ users.php?user=$1 [NC,L]

#error codes
RewriteRule ^/error/([^/]+)/ error.php?code=$1 [NC]

Change your .htaccess to the following:

RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d    
RewriteRule ^users/([^/]+)$ users.php?user=$1 [NC,L]

Also make sure users.php is in a right directory. If it's in root directory, you can use:

RewriteRule ^users/([^/]+)$ /users.php?user=$1 [NC,L]