As the processor isn't working very hard, swapping it for a more powerful one won't increase the responsiveness of your site very much. (Unless you are running very processor intensive scripts!)
As you already suspect, the amount of RAM, the bus speed, and the HD access time and data transfer rate are the determining factors for your server's performance.
What reason did your host give for the upgrade, is it just that they have a boxes of unused P4's kicking around ;-)
Would they ley you try one for a few days, so you can assess the performance jump for yourself?