A reasonably common issue with imagecache seems to be arising when people have tried to move a site from one host (or a development platform) to a live host.
There are several causes for this, and most are just versions of the troubleshooting steps involved and already documented. When changing servers, You have to check each of those settings again!

• Symptoms:
  is_file() [function.is-file]: open_basedir restriction in effect. File(/usr/bin/convert) is not within the allowed path(s)
The specified ImageMagick path /usr/bin/convert does not exist.
  Check the available image toolkits. If you chose to use ImageMagick in development, and the destination doesn't have or allow access to it, you are out of luck. ImageMagick support on cheap hosts is quite rare.
  Solution:
  Switch back to GD (if possible).
• Symptoms:
  mkdir() [function.mkdir]: Permission denied
mkdir() [function.mkdir]: File exists
  This is simply - as indicated, a permissions problem. This can occur if you've copied the files over by FTP or from backup ... depending on many things (like umask) copied files may not be re-created with their original permissions. This is quite normal, and is a factor of your hosting environment and access level.
  Although everything in the /files directory was made writable to Drupal during development, this permission was lost when you logged in via FTP and made those dirs with your user account.
  Solution:
  • Fix it: Grant global (or group) write permissions to everything under /files.
  • Don't mess it up again. Possible fixes include:
    • Using tar to bundle your files, then unbundle them again on the destination is not only more efficient, but it attempts to maintain file permissions in the process. This may not actually help with hosted servers where the apache process is a different username, but it may.
    • Configure your FTP client to maintain permissions. This depends on your client, but may be possible.
    • Modify your umask for your account on the server or the "sticky bit" of the directory to share ownership of created files. This is tricky and best left to platform-specific docs.
    • Use a different method to deploy your files. If you can, rsync -a is a much more reliable way of keeping folders in sync than FTP, and will retain not just permissions but timestamps and all.
• Clean URLs. Of course, if you had clean URLs on, and move to a host where they are off, you will have trouble and need to unset or repair the clean URLs setting on the host. But you will have already discovered that when all your other links stopped working.
• Other file problems:
  As already documented - the temp directory has to be correct. This is auto-detected when you installed Drupal but not automatically changed when you move the configuration to a different environment. You may need to fix that up.
• Failure, no error
  As before, you may need to check your PHP memory limit is high enough. You are on a new site? Those configs may be different now!