I built a new pc and tried to power it up. It turned on but displayed this message: "Warning! CPU has been changed or CPU Ratio changed fail. Please re-enter CPU settings in the CMOS setup and remeber to save before quit"

I go into the cmos/ bios and the computer shuts down. It seems like no matter what I do I only have ~45 seconds untill it shuts down.

The motherboard and processor are:

MSI PM8M3-V Socket 775 Motherboard
Intel Celeron 351 3.20Ghz 533FSB Socket 775

Did you bench test prior to putting everything together ?

Remove the power lead and CMOS battery for 10 minutes, then put them back and the BIOS should default to factory settings....

does it shut down automatically as it is overheating? (heatsink/fan fitted properly and thermal paste there?)

Did you make sure the cpu you are trying to use is on the cpu support list for this mboard? Even if you did, your cpu may not be supported by the bios version that is on your mboard, which may be a lot older that the newest available on the website, and the bios can't recognize the cpu. In that case, if you are sure the cpu is supported, you have to temporaily install a cpu that works no problem, flash your bios, then install the cpu you want to use.

Make sure any jumper on the mboard for upping the cpu voltage for overclocking the cpu is not in the overclock position (that is usually in the "normal" position when you get a new mboard, but I installed a MSI mboard not long ago that had it in the wrong position).

On many recent mboards you must have a 3 wire fan connected to the 3 pin header for the cpu fan - if no rpm is detected within a very short time after booting, the mboard will shut down.
Also, if the cpu fan you are trying to use is one that spins a lot slower than the hardware monitor expects, some mboards will shut down because they sense the rpm is too low or zero.

Even if your mboard doesn't have that protection, most mboards will also shut down if you have installed the heatsink on the cpu incorrectly, or the fan is not spinning, and the cpu temperature gets too high, but it usually takes minutes for it to do that, not seconds.

""Warning! CPU has been changed or CPU Ratio changed fail. Please re-enter CPU settings in the CMOS setup and remeber to save before quit"

I have noted that on some computers you will falsely get a message like this if you merely press the key to get into the bios at the wrong time or if you hold down the key while booting - when you go into the bios in that case, the cpu settings are okay when you check them and you merely save settings and everything is fine.
You are supposed to repeatedly press the key to get into the bios, not hold it down, just after the ram has been counted.

It is also possible to falsely get a message like this if something else is wrong, such as a keyboard error, but the cpu settings will be fine when you look at them.

It doesn't seem to be overheating. Everything seems to be mounted ok. I'm using a fan and heatsink (Masscool 8W0141B Socket 775 CPU Cooling Fan 3.6GHz). I'll have to check out the compatability and see if i can reset the bi

If the bios version can't recognize the cpu you have, you can't cure this problem by changing bios settings. It should recognize the cpu just fine with default bios settings. If it doesn't find any settings for the cpu, either the bios needs to be updated, your mboard cannot recognize the cpu whatever bios version you have, or, very unlikely, the cpu is defective.
....

"Make sure any jumper on the mboard for upping the cpu voltage for overclocking the cpu is not in the overclock position (that is usually in the "normal" position when you get a new mboard, but I installed a MSI mboard not long ago that had it in the wrong position)."

NOTE that the higher cpu voltage did NOT show up in the current voltages displayed in the bios. The hardware monitor sensor for that apparently wasn't hooked up in the right place to be able to measure the increased voltage. What I noticed first was the cpu was getting hotter than it should even at idle, and when I checked the mboard manual I found that the jumper was in the wrong position. When I moved the jumper to the normal position the cpu temp immediately dropped to the normal values expected.
....

Most recent mboards require you plug in the main connector from the PS AND another power connector from the PS, in another place on the mboard, often a 4 pin one - did you do that?
Some recent mboards require a 24 pin main connector from the PS and will not work properly with a 20 pin one - some can use either. If you have a 20 pin main connector from the PS and you must have a 24pin one for the mboard, or your PS doesn't have the extra power connector to the mboard required, wiring adapters are widely available at smaller places that build custom computers that will adapt to what you need. Many newer PS's come with a 20 pin main connector and a 4 pin connector that can clip on the end of the 20 pin one to make it a 24 pin main connector.