Changed CPUs and new processor won't boot with 4gb ram

I'm putting this here because seeing as the processor was the part that I replaced most recently, I'm blaming it.

I replaced my CPU about two weeks ago. I went from an E4500 to a Q9400. I use a Gigabyte EP45-UD3R (upgraded from an ASUS P5N32-SLI Premium/WiFi, and have until now used nothing but ASUS boards), and for whatever reason, whenever Ij try to use all 4gb of my RAM with the new processor, system boots and then freezes halfway through the BIOS loading screen. I know all 4 sticks are good as I have tested them individually with no problems, and in each of the different DIMM slots (I once had a board that had two dead slots, so I learned to check for repeat offenders). All 4 sticks are OCZ, but they are running at two different speeds (2x 800MHz and 2x 667MHz; each pair came matched from a 2 gig set). Currently I am running on the 800MHz sticks, but I would like to see if there was something else I could do before I go out and spend the money on more memory if I don't have to (what especially puzzles me is that on it booted just fine like this with the E4500 - I pulled the new processor out and tested it to make sure).

Any help anyone can give me would be most appreciated.

I think you can if your mobo supports the speeds. The faster RAM downclocks to the speed of the slower RAM.

You changed mobos, different chipsets... Did you repair/reinstall windows? Mobo change will most likely cause some ill effects if windows isn't 'refreshed'.

When you changed cpus, did you update and/or reset the bios (and if you didn't, you should)? Newer BIOS might have better compatibility with new CPUs. Updating the bios will most likely reset the settings to default, so use the memory timing settings from the slowest pair and give them enough voltage to run both.

What PSU do you have?

edit and you can mix ram speeds, you'll just need to find and force such settings that both pairs will work under them

UPDATE: I finally updated to the latest available revision of my BIOS (F9), and I am still having the same issues. I am thinking it is either the board (I DID pick it up open box on Newegg, meaning that someone else had to return it for whatever reason, and I have had boards with dead ram slots before) or the memory sticks (much less likely, but given my luck with hardware, I wouldn't discount it as a possibility).

Have you tested each stick individually?