Gracias a todos por vuestros post.
Al final parece ser que habia algo mal instalado, o que creaba conflicto, aunque lo habia reinstalado varias veces sin conseguir solucionarlo.
Esta vez lo he limpiado bien todo, he instalado la aplicacion Foxserv, despues he actualizado php a la version 4.3.9, venia la 4.0 por defecto, luego también he actualizado Mysql y phpmyadmin y ahora las sesiones funcionan perfectamente.
Lo único que algo no habré hecho bien al actualizar Mysql porque ahora no me deja conectar a la base de datos desde script y si desde phpmyadmin
pero bueno, ese es otro tema.
[Edito]: Ya he solucionado este último problema, que eran dos, el primero que no me mostraba los mensajes de error, cambiandolo en el php.ini y ya está, y el otra buscando en el foro, un post de josemi me ayudo, no habia creado un usuario para acceder a la base de datos.