Tried both sticks in combination with one of the original 2GB sticks, both work just fine. It's just when there are two 4gb 1333 sticks. When there is a 1066 stick present, the other stick will downclock to match it, but when there are two 1333 sticks, it just won't boot.
The workaround is to flash one stick to be recognized as 1066 so that the other one will downclock, but that involves buying $22 software to do so. Otherwise, I would just flash it myself.