There are a few possibilities/solutions:
1., The
manufacturer's site states that PC4000 (DDR500) is only achievable when it's set to 3-4-4-8. Now it is possible ofc that it would also work on lower settings but I would give it a try. So set the mem params manually instead of auto config (if you haven't tried it yet). Also set command rate to 2 (for the test, if it works well then you can try to set it to 1 to test it).
2., You didn't state as to which config you have: 2x512MB or 4x256MB. I assume that you have the 2x512MB. In the other case the four-module configuration may not work very well on tight memory settings especially when the command rate is set to 1.
3., It may has nothing to do with your memory settings at all. Have you set the PCI clock to fixed? Maybe it's just your controller can't boot your drive because of the very high PCI clock.
4., Download
MEMTEST and boot it from CD. Run it and see if your memory fails.
5., Don't know.