Hello Rattus: I tried everything you suggested and more. The PHP Memory Limit is above 200Mb and the GD Library is also installed!
The error message is not with all thumbnails just with a few random ones – please take a look at http://www.tashaschuh.com and click on the right sidebar photo gallery.
Please help :-(