Are you sure your temps are ok? The reason for it being slower could be that the CPU is throttling the speed in order to try and keep the temperature down. HWMonitor is a handy tool that will monitor your temperatures:
It would be nice if you listed your computer specs, what your OC clocks are, and what you used to overclock (BIOS, program, etc), so we can help understand your situation.
mmmmmm technically if you OC depending on specs and OC'd stats you can *LOOSE* performance if your ram has to drop alot or de-sync everything etc - benchmarks and stability tests are your friends - i suggest use them and do it properly or dont bother at all
It sounds like if you're having issues while booting then you don't have a stable overclock. I had this issue before when I tried overclocking an older system I had that just wasn't suitable for overclocking. It took longer to boot until I dropped the speeds back down to normal. Really you need to have a motherboard that overclocks well, a good solid PSU and a good cooling solution.
Yes, you're motherboard does support DDR2-800 so this would be a viable upgrade. It still won't guarantee that you will have better luck overclocking though since as I said in a previous post successful overclocking depends on a lot of factors.
Having said that, a jump to 4GB DDR2-800 from your current RAM would see a pretty big performance boost.