I have just had a lot of trouble with Thumbnails on one of my blogs. It turned out that I had to install the package php5-gd and restart Apache before thumbnails would even be generated. The package php5-gd (or php4-gd) is “suggested” by the Debian WordPress package and it’s not a dependency, so the result of apt-get install wordpress will be that thumbnails won’t work.
I’ve filed Debian bug report 447492  requesting that php5-gd be a dependency. Another slightly controversial issue is the fact that the MySQL server is not a dependency. I believe that it’s correct to suggest MySQL as the database server is commonly run on a different host and WordPress will clearly inform you if it can’t access the database.
An alternate way of solving this bug report would be to have WordPress give a warning such as “Thumbnails disabled due to lack of php-gd support” which would allow users to make requests of their sys-admins that can be easily granted.