I’ve seen this error occasionally, but recently it has caused me some grief, so I finally decided to look it up.
In Debian and Ubuntu, /var/lib/php5, where the session data is stored, has permissions of drwx-wx-wt and should only be cleaned by a cron script. So, the package maintainers disable automatic session garbage collection.
The article linked gives some great background, and the answer seems to be setting
session.gc_probability = 0.