Available disk free space isn't necessarily an indicator. To put it in DOS/Windows OS terms, *nix systems are subject to the same "too many open files" issues -- that is, you can run out of file handles long before you run out of disk space. Or, to relate it to the older Windows versions, you can use up the resource block of memory and get an "out of memory" error, even though you might have several MB of unused RAM.
If you've had some situation that results in a large number of files being opened -- runaway spoolers are noted for this -- then you can run out of (again, in DOS/Windows terms) "file handles". This, I believe, is what the "free list empty" error is reporting -- the fact that the *nix kernel can have only a finite number of files open, and for whatever reason that limit has been reached.
Note that it is also possible to run out of inodes, which are roughly (not exactly) equivalent to directory entries. Think of them as directory entries, except without the name itself, which resides elsewhere. There are a finite number of inodes available on a file system. If you install a gazillion small files, or have an application that goes wild creating tmp files, then you can easily run out of inodes before you run out of free disk space.
Both the free list and inode table are static, meaning the kernel and filesystem have the size established ahead of time and do not dynamically grow them to fit. Tunable parameters, as it were. Usually, changing the free list table requires recompiling the kernel, and setting the available inodes can only be done when the filesystem is created.
In your case, I'd be looking for something that is opening and holding open lots of files. Maybe something breaking a large file into smaller chunks, or a daemon that is spawning and hanging prolifically, etc.
Scott