Chmods were the first things I checked, all good. During my fiddling around with this, however, I found some stuff:
(Note that, at the start, Upload path and download URL base was 'downloads' and thumbnail path was 'downloads/thumbs'. Also, I'm not exactly one to leave things alone ... o.O)
1. If I tried to create a category (let's call it 'cat') with no thumb, it worked fine, as far as I could see.
2. If I tried to add a thumb, I got the same error BUT the path would be changed from "cat" to "cat2" for some reason.
3. If I created and then modified it (see #1, above) I would have "cat" and "cat2" folders in the /thumbs/ directory.
4. If I tried to make a category with a thumb and failed, a look in the /downloads/thumbs/ directory showed no new 'cat' folder; only the folders from previously created categories, all of which were created with no trouble.
5. Neither method resulted in a "caticon" file being made.
6. So, I tried manually uploading an image to the folder (why not?), naming it "caticon" and then modifying the category... worked fine.
7. Everything in /downloads/ was 777, /downloads/thumbs/ was all 777 EXCEPT for the directories created without icons (#1, above), those were 755 (huh?).
8. Decided "f*** it, what have I got to lose?" and deleted the thumbnail path from >settings>misc ... everything's jolly now. Works like a charm.
Beats the hell outta me...
Bear in mind that everything worked fine and dandy in the beginning. I was totally in the middle of getting some serious "holy s***, this thing's f***ing great!" wood when it up and barfed on me. The ONLY thing that had changed, was that I disabled download permalinks in >settings>download because I was getting a buttload of 404s. Re-enabling it didn't fix anything, though.
So, in other words, I have NO idea what the hell happened. But it works now, so I'm not gonna go pickin' at it...