So what does your .htaccess file say? It sounds like somewhere along the line Apache is preventing itself from creating or serving the images (haven't figured out which, yet).

Also, imagecache requires Clean URLs and the Public Filesystem in the Drupal settings. It sounds like you've already done that, but it doesn't hurt to be sure.