Optimization is not really something that should be guessed at. Instead you need to measure what is going on to determine the chokepoints and where changes need to be made.
A faster processor may have little or no effect especially since the CPU utilization is not maxed out. CPU speed affects only those parts of the program which are actually running on the CPU. If the program is waiting for something else such as an I/O operation, a faster CPU doesn't help. The chokepoint is not the CPU speed but rather the I/O speed.
So you may have a faster CPU but that just means that your program gets to a place where it has to wait for something else to happen a bit faster. If your program requires user input then no matter how fast the CPU, the program is still bounded by the speed of a human doing the input.
Program speed also is affected by the algorithms being used. A faster CPU may help a bad algorithm go faster, a kind of linear increase, a better algorithm may provide several orders of magnitude improvement in speed and performance.
Another possible throughput increase can come from multi-threading. This only really helps if you can divide out the overall problem into multiple, asynchronous tasks that can be run simultaneously and the results of each task combined when all are done. The more need there is for synchronizing tasks and events the more likely that multi-threading will not provide that much of an improvement.
With multi-threading there is always the question of how many separately running cores are in the CPU or how many CPUs are being used for the program.
Multi-threading with a single core on a single CPU may or may not help since the various threads are sharing the same core and CPU. It depends on whether some threads are able to progress while other threads are waiting for some resource or event to happen such as I/O to complete.
If you are able to divide out the program into multiple threads and assign the different threads to different CPU cores or multiple processes and assign the different processes to different CPUs then more things can be happening simultaneously. However if all those threads are not compute intensive and are waiting rather than running then it may not make that much difference.
Finally the actual hardware design can make a large difference in the throughput of a CPU. Overclocking a CPU means that it is running faster however it is the same hardware. The differences in throughput between various CPU generations is not due to just CPU clock speed. There are also hardware improvements so that two CPUs with the same clock speed will show very different processing throughput because the hardware design of one is superior to the other. This is where design details such as branch prediction, prefetch, size of the onboard cache, and other hardware details really make a difference.