Hello there, did you replace the battery through an outside source (other than apple)? if so then you may want to first make sure that the battery is FULLY charged prior to any usage of your laptop. Also, any 3rd party software or Itunes songs that you added yourself will cause a software issue that will make it shutdown randomly as well. Batteries other than the apple designated ones will work but the Mac does not like them and it could result in a random shutdown too. When you get it up again look in the kernel log and look for "Shutdown Cause," there will be either a 0 or -82 number you will see. That is usually related to a hardware issue. If it appears to run stable for at least an hour then go ahead and run the apple hardware test from disk #1 (do the extended test). Please use a firewire optical drive if you have one, I have found that you have less problems with shutdows while you are running the test.
Now this test is NOT totally full-proof but it will detect the obvious problems if there are any. Otherwise you can take it to a Apple store and ask them about this program that they are offering to have your machine repaired for the total cost of $350.00 That cost is suppose to include whatever parts the machine needs, I forgot the name of this program that Apple is offering (something about a "Depot" Program I guessing). Anyways you can call the store and ask them about it.