After a lot of trial and error, it turns out the problem was the size of the source images.

Explanation
We make each of our product images is available in high resolution for subsequent download by customers, so we were using the hi res images (2100x2165px and about 400KB each) as our initial product image upload.
These hi res images would upload successfully, but the scaling function used by imagecache would fail - and therefore the category and product pages would not appear.

Workaround
I manually scaled the images to a lower resolution and size and re-uploaded and it worked.

Interestingly, this worked well on our development server (a physically different machine).

I wasn't able to find a specific reference about file size/resolution limitations. Any thoughts?

I hope this can help someone.