It would be cheaper to buy a new notebook than to by an "HP Certified CPU". The Certified CPU is the exact same CPU you would by retail, the only difference is the
----The particular model and operating frequency is known by HP to work in that model of the notebook.
----It comes with a 2 cent white label glued onto it saying "HP" and with an official HP part number making it what they call "white label" and supported by HP for warranty service.
Best bet is to go to the HP website and see what CPU's were offered with your notebook.
If you are going say from a 1.2Ghz Banias to a 1.7Ghz Dothan and your model line from HP was never sold with say anything better than a 1.5Ghz Banias then you will have some risk for compatibility issues, especially with the BIOS.
If your model line has/had been sold with a 1.7GHz or faster Dothan then the chances of it working are great.
Before I would jump to updating BIOS (don't break what is not fixed) have you considered that your power management settings are limiting your speed.
If you have it set to notebook or max power savings or a few others then the CPU clock multiplier will be less. For instance on notebook the CPU frequency decreases when CPU load is small and goes up when CPU load increases. On max battery setting the CPU frequency is locked to the lowest performance setting. You can set it to desktop or minimal power savings and have the full clock of the CPU available.
Also consider running an App like Prime95 as that highly stresses the CPU and if you are say on notebook power management setting you will see the operating frequency go up.
Alternatively alot of the HP notebooks can have this feature totally disabled in BIOS by pushing F10 during boot then navigating through the menu with your arrow keys and choosing the one that says disable power management/run a max performance or something like that.
I am thinking it is more likely the power management because lack of BIOS support will usually result in no boot of the machine but I have seen it the other way also with the symptoms you describe, just left often.
If you update BIOS though take care, its easy to kill the machine by being lazy and not following the instructions exactly, or having an unstable machine prone to freezes and slow bootup or other things like that, or just your day for bad luck.
If you are under warranty though its probably best to update BIOS just before warranty expires.