Version:            (using KDE 4.4.1)
OS:                Linux
Installed from:    openSUSE RPMs

I have made the following observation:
digikam reported that the dustbin is full and should be emptied manually. The dustbin was set to use 10% of the hdd, which was about 60 GB. It also should remove files older than 120 days. I hadn't undergone a thorough deletion party recently with several GB of size, just the usual. So I would think that the dustbin couldn't be full, because it would have removed files older than 120 days and thus provided space again. 
I removed some files from the dustbin (about 200 MB) by clicking on it and deleting the files from within dolphin. However, digikam didn't stop complaining. I deleted more files, still no success. I then increased the space for the dustbin available (to 20%, i.e. 120 GB), also no change. The hdd had about 360 GB free space. 
Eventually, I had to empty the dustbin completely by clicking on "empty dustbin" in the context menu. However, I would have preferred to keep some of the recently deleted files, because one is never sure...
The important thing is: I couldn't get rid of the "dustbin full" message except by completely emptying the dustbin, even though the dustbin was set to remove older files before it reaches its set limits, and even though it hadn't reached the limit.
Unfortunately I didn't think of testing this in other apps which use the dustbin, whether they also would produce the "dustbin full" message. But I guess they would have.