Can’t create thumbnails for large images

Here’s a problem I really do not understand: I can’t create thumbnails for large images, although they get uploaded correctly. What happens is that if I only upload a large file (and yes, I have changed the default value for allowable uploads under “Options”), everything works perfectly. However, when I also check the “Create a thumbnail?” option, the file gets uploaded, but no thumbnail is created, and WordPress does not change page to the “File uploaded!” page.
Has anyone encountered similar problems? And, more importantly, does anyone have a solution to this problem?