Please try using this CVS snapshot:

  http://snaps.php.net/php4-latest.tar.gz
 
For Windows:
 
  http://snaps.php.net/win32/php4-win32-latest.zip

I've got the same symptoms, only system is diffrent.
I'm using PLD Linux 1.0 (kernel 2.4.19) with PHP 4.2.3

Info displayed on my page (it is shown only ocassionaly,
not every time):

Notice: ps_files_cleanup_dir: opendir(/var/run/php) failed: Permission denied (13) in /home/php-include/default/ThLogin.inc on line 55

Line 55 contains a session_start(); only.

Below are some infos generated by phpInfo:
(maybe this will help somebody)

SystemLinux ep09 2.2.21 #1 SMP Mon Aug 19 22:15:18 UTC 2002 i686 Pentium_III_(Coppermine) unknown PLD Linux Build DateOct 21 2002 15:26:41 Configure Command './configure' 'LDFLAGS=-s' 'CFLAGS=-O2 -march=i686 -DEAPI=1 -I/usr/X11R6/include' 'CXXFLAGS=-O2 -march=i686' 'FFLAGS=-O2 -march=i686' 'CPPFLAGS=' 'CC=i686-pld-linux-gcc' 'CXX=g++' '--build=i686-pld-linux' '--prefix=/usr' '--exec-prefix=/usr' '--bindir=/usr/bin' '--sbindir=/usr/sbin' '--sysconfdir=/etc/php' '--datadir=/usr/share' '--includedir=/usr/include' '--libdir=/usr/lib' '--libexecdir=/usr/lib' '--localstatedir=/var' '--sharedstatedir=/usr/com' '--mandir=/usr/share/man' '--infodir=/usr/share/info' '--with-apxs=/usr/sbin/apxs' '--with-config-file-path=/etc/php' '--with-exec-dir=/usr/bin' '--disable-debug' '--enable-bcmath=shared' '--enable-calendar=shared' '--disable-cli' '--enable-ctype=shared' '--enable-dba=shared' '--enable-dbx=shared' '--enable-dio=shared' '--enable-exif=shared' '--enable-ftp=shared' '--enable-gd-native-ttf' '--enable-magic-quotes' '--enable-mbstring=shared' '--disable-mbstr-enc-trans' '--enable-mbregex' '--enable-overload=shared' '--disable-pcntl' '--enable-posix=shared' '--enable-session' '--enable-shared' '--enable-shmop=shared' '--enable-sysvsem=shared' '--enable-sysvshm=shared' '--enable-track-vars' '--enable-trans-sid' '--enable-safe-mode' '--enable-sockets=shared' '--enable-ucd-snmp-hack' '--enable-wddx=shared' '--enable-xml=shared' '--enable-xslt=shared' '--enable-yp=shared' '--with-bz2=shared' '--with-cpdflib=shared' '--with-crack=shared' '--with-curl=shared' '--without-db2' '--with-db3' '--with-dbase=shared' '--with-dom=shared' '--with-dom-xslt=shared' '--with-dom-exslt=shared' '--with-expat-dir=shared,/usr' '--with-iconv=shared' '--with-filepro=shared' '--with-freetype-dir=shared' '--with-gettext=shared' '--with-gd=shared' '--with-gdbm' '--with-gmp=shared' '--with-hyperwave=shared' '--with-imap=shared' '--with-imap-ssl' '--with-jpeg-dir=shared,/usr' '--with-ldap=shared' '--with-mcal=shared,/usr' '--with-mcrypt=shared' '--with-mhash=shared' '--with-ming=shared' '--with-mm' '--with-mnogosearch=shared,/usr' '--with-msession=shared' '--with-mysql=shared,/usr' '--with-mysql-sock=/var/lib/mysql/mysql.sock' '--with-openssl=shared' '--with-pcre-regex=shared' '--with-pdflib=shared' '--with-pear=/usr/share/pear' '--with-pgsql=shared,/usr' '--with-png-dir=shared,/usr' '--with-pspell=shared' '--with-recode=shared' '--with-regex=php' '--with-sablot-js=shared,no' '--with-snmp=shared' '--with-sybase-ct=shared,/usr' '--with-t1lib=shared' '--with-tiff-dir=shared,/usr' '--with-unixODBC=shared' '--with-xmlrpc=shared,/usr' '--with-xslt-sablot=shared' '--with-yaz=shared' '--with-zip=shared' '--with-zlib=shared' '--with-zlib-dir=shared'

No feedback was provided for this bug for over 2 weeks, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".

I also experienced this issue running PHP 4.3.4 on Debian.  I resolved it by removing the sticky bit on the sessions directory (`chmod a-t /var/lib/php4`), although obviously this has security implications.

False call on the above comment.  It's still happening.

I had the same problem with apache 1.3.29 and php 4.3.4 and also with apache 1.3.31 and php 4.3.8 on debian testing / unstable.

The PHP notice was

Notice: session_start(): ps_files_cleanup_dir: opendir(/var/lib/php4) failed: Permission denied (13) in  ...

It only occurred every so often.  I think I have discovered the cause. In order to reproduce this consistently; update these parts of your php.ini file to:

session.gc_probability = 1
;session.gc_divisor     = 100
session.gc_divisor     = 1

and restart apache of course.

Changing the probability of the garbage collection routines to 100% cause this to happen every time session_start() is called.
I'm guessing that the session file is locked by session_start() and that the garbage collection routine ps_files_cleanup_dir? is failing?

As this doesn't seem to affect the sessions a solution would be to prepend an @ to session_start() to suppress notices/errors/etc or to do you own garbage collection as suggested in the php.ini file.

I hope this helps someone as I spent a good 6 hours hunting it down :-).

Mike Miller.

It turns out to be a distro problem: A debian person explained it to me: 

Re: Bug#256831: session-dir permission problem

I'm sorry to hear that.  The cause of this bug is already known: for security reasons, session files are now stored in a directory that is only readable by root, which means that PHP scripts running in either the webserver security context (user www-data) or as a per-user CGI will be unable to get a list of session files in the directory.  This is by design, and will not be changed; what will be changed is to disable PHP's internal session gc and replace it with a cronjob running as root that can sweep the directory on our behalf.

To reiterate,

This is a(nother) Debian packaging problem. The bug report is here:
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=256831

The fix this,
session.gc_probability = 1
session.gc_divisor     = 100000000

(Note: once in a billion hits, someone will get an error message)

Then, set up your own garbage collection. This is discussed already in php.ini.