I just built my new rig and the CPU is at 76c in Bios?? Processor is FX-6300 at stock speeds with stock cooling.

Stock cooling is most likely why it's temps are at where they are, likely, the FX line 6xxx and up get hot as far as I know. 

But 76c in bios? Thats not right.

I dont know the general temps on that chip, but from how hot those go, I wouldnt be surprised if that is normal with the stock heatsink. if its the stock watercooling kit version, then I'd be really worried.

Well, seeing as how the max safe temp for the cpu is 62 and 71 for the socket, either I have a molten chip or the bios are wrong.

Remember AMD is notorious for weird temp senors as well so it could be the sensor is malfunctioning, mine cooled way down after I got an OS on it and got the chipset drivers up and running

That may be it. I havent installed drivers for anything yet. When windows finishes, I'll give an update. 

My A10 ran 66°C in bios but after I installed drivers it cooled down to 45°C, AMD sensors still suck my IGPU reads -4°C idle

66c to 45c is good, but im on the threshold of failure

90°C is panic time, 70°C is an optimal load temperature most of the time, I would start to get cautious at 80°C but 70°C doesn't normally hurt anything

I will remain cautious until I see it drop. Is it normal for it to be so hot?

better thermal paste and cooler? 

or go cheep and cool the hell out of your entire pc with extra fans

I would say be cautious for now, but get an upgrade to the cooling soon, hyper 212 EVO or H60 (their both relatively cheap and should get you on the ground and running until you can get some serious cooling on it (only if you want to OC, if not the H60 will give you 2 years and Hyper 212 EVO will last forever, but it doesn't cool quite as well as an H60 but margin is less than 10°C)

I have 3 140mm 1 120mm and 3 80mm in the case. 2 140mm on top for exhaust, a 120 in back for exhaust, 140 in front for intake, 2 80s in basement for exhaust, and 1 80 in front of basement for intake