Check the value of innodb_thread_concurrency.
For my system increasing the value from 8 to 32, per the guidelines in the MySql documentation, caused a discernible decrease in the number of threads concurrently reporting the "freeing items" state. Also, the obesrved average query time dropped by an order of magnitude.
While this made a large difference in overall server performance, it was not the "freeing items" silver bullet. My hardware ecosystem leads me to hypothesize that this state is mostly seen on systems with "slow" disks (2x10k disks raid 1), and is less prevalent on systems with faster storage (12x15k disks raid 10). So, a check of disk performance may also be warranted.
It is worth noting that the default value of innodb_thread_concurrency is radically different depending on what 5.0 point release is being used.
The default value has changed several times: 8 before MySQL 5.0.8, 20 (infinite) from 5.0.8 through 5.0.18, 0 (infinite) from 5.0.19 to 5.0.20, and 8 (finite) from 5.0.21 on. -- source
This means that a seemingly innocuous upgrade from 5.0.20 to 5.0.21 changed the default from infinite to 8, and brought along with it the performance ramifications.