> Threading, if done correctly, should help on the new machine, correct?
It should - but you need to check some details of your specific OS and threading implementation. You might end up with different processes running on different processors, but threads within a process all stuck on the same processor (not a good thing).
If the split is only at the process level, then one process per job will get the work spread over all the processors, and solve the thread-safe problems with MySQL you highlighted previously.

> that converts various image formats to eps
What's your hard disk utilisation like when this is happening?
If it's pretty high on your single CPU solution, then its going to be a serious bottleneck on your quad-CPU solution.
However, watch you don't get all that abberant swap behaviour mixed in with any of your disk usage stats.

> the cron jobs begin to overlap,
Would detecting this and backing off the 2nd cron help?
A 'simple'
Code:
if [ last_cron_not_done ]; then exit ; fi
Implementing last_cron_not_done is an easy exercise for the reader

Or maybe a loop around that which sleeps periodically (say 10 seconds) for up to a total of 5 minutes before finally exiting (when the next cron will start anyway)

> all the memory is consumed (one of the libraries has a leak in it) and kswapd starts going nuts
Unless this gets fixed in the new machine, then the cron backoff idea above would be needed anyway. At best you're only going to defer the same problem from happening again. If the workload catches up to the machine again, you'll be back in the same problem.

> converts various image formats to eps, which is the meat of the problem.
Ah, sounds like the PERL is just a wrapper around this then. If it's fairly simple PERL, and not much of it, then I doubt you'll get much benefit out of trying to optimise that.
The C code on the other hand would seem to be definitely worth further attention. 'gprof' is the profiler for C code.
Gather some test data (some simple, some complex) and feed that into a profiled version of the C code. Make sure you have a couple of examples of each kind of image format (one type may be much more expensive in comparison to other formats).

I can't answer your last question - I don't know nearly enough C++ to comment.
Exceptions are pretty new to C++, and pretty complex in their own right. Mixing all that up with threads is probably too experimental for something which you regard as being pretty mission critical.