"Unable to generate the derived image located at public://styles/uc_category/public/tg.jpg" (Drupal 7 under Linux)

This is clearly a Drupal permissions problem, but I'm baffled. If I 

rm -rf styles


and refresh the page causing the error, styles and it's sub-dirs are re-created thus:

drwxr-xr-x 3 www-data www-data 4096 Jan 25 16:07 styles

drwxr-xr-x 3 www-data www-data 4096 Jan 25 16:07 uc_category

drwxrwxr-x 2 www-data www-data 4096 Jan 25 16:07 public


But I still get the error. And I still get it if I

chmod -R 777 styles


Any suggestions?
If you are sure this is not a permission issue, also make sure you have a graphical library installed on your server.

In D7, the configuration page for this is: /admin/config/media/image-toolkit