El error completo sera algo como:

PHP Warning: Unknown(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/tmp/) in Unknown on line 0
PHP Warning: Unknown(): open(/tmp/sess_404b65f5a6f22fd57694ce1442af5769, O_RDWR) failed: No such file or directory (2) in Unknown on line 0
PHP Warning: session_start() [<a href='function.session-start'>function.session-start</a>]: open(/tmp/sess_404b65f5a6f22fd57694ce1442af5769, O_RDWR) failed: No such file or directory (2)

Las session en php, son simplemente una cookie, pero que se almacena en servidor. Y una cookie es simplemente un fichero de texto con un hash y variables con datos.

Creo que todo esta bien, salvo que no asignas un session_name() para el session_start() y puede darse que al no asignar un nombre especifico, se use un genérico, que tiene la forma sess_(un hash) y se use un fichero de session aleatorio que haya dado colisión con otro que haya sido creado por otro usuario que lo este usando también sin establecer nombre.

¿y porque se da el error? Porque estas viendo una página "cacheada" en tu navegador y el servidor tiene asignada esa cookie-session a otro usuario, por eso de dice que no tienes permisos. La solución seria borrar la cache, pero aunque es un apaño, la culpa no la tiene el usuario, esta en el servidor por haber asignado esa cookie-session a otro usuario previamente no haber liberado la cookie-session.

En ingles lo dicen como "in the belief that somehow the two people were getting the same ID and hence temp file"

Te puedo decir, que ese error, nos ha dado hasta en nuestra web principal y nosotros que tenemos experiencia en programación ya nos había resultado raro. Pero esto es un problema que esta generando PHP con phpsuexec

Buscando en google, aparentemente no hay soluciones, pero si encontramos que había reportes de bug en el bugtracker de PHP:
http://bugs.php.net/bug.php?id=19022 (BUG PADRE)
Otros bugs relacionados:
http://bugs.php.net/bug.php?id=43990
http://bugs.php.net/bug.php?id=5370

Si observas las respuestas de google de otros hosting, su solucion es "contrata a un mejor sysadmin", "TU estas haciendo algo mal", "comprueba tu configuración", "Asked sys admin to fix it" , pero no dicen porque ni dan soluciones, eso es para evitar decir que NO tienen solución, si saben como arreglarlo, aquí en Quijost no engañamos a nuestros usuarios de tal modo.

Las únicas soluciones que se dan son:

1 - Reiniciar la máquina (MALA solución: tratándose de servidores en producción no se puede jugar con el uptime y más si se da espontánea y periódicamente)

2 - rm -rf /tmp/sess_* (MEDIA solución: no requiere reinicio, pero hace perder el logueo a todos los usuarios que estén en el servidor para arreglar al resto, aparte habría que ejecutarla cada vez que da este error que puede ser en cualquier momento y sin posibilidad de detectar cuando)

3 - Modificar el directorio donde se guardan las sessiones a uno del usuario para asi que no den problemas de permisos:
ini_set('session.save_handler', 'files');
O bien un directorio del usuario (creando un directorio tmp en el directorio del usuario):
ini_set('session.save_path', '/home/usuario/tmp');

Documentacion:
session_save_path()
www.php.net/session_save_path

4 - Aparte puedes poner este trozo de código para evitar que te de error en el session_start():

if(@session_start() == false){session_destroy();session_start();}

Pero lo que hacemos es borrar la sessión actual y generar otra.

5 - Pero la mejor solución seria ponerle un nombre a la sessión para que no diera problemas
 
session_name('myuser'.rand());
session_start();

Aunque habría que generar un identificador único, porque ese podría coincidir.

Como ves, esas son todas las opciones, pero lo suyo sería que PHP arreglase este bug, que se da en muchos, por no decir todos los sitios que usen sesiones y eso son millones.

Espero que te haya resultado útil la respuesta. La voy a postear en mi blog con el fin de que salga en google y haga mas presion en el bug de php.

shakaran espectacular post, me ha servido de gran ayuda

muchas gracias!!!