Your are right, seems your PC doesn't like running at 800 (actually ay 400 in the BIOS), but will run at the slower speed. When you mix speeds and the BIOS memory settings are set to AUTO, the system will default to the lowest common denominator in terms of speed to a compatible level.
You can manually adjust the memory settings in your BIOS (with one of the new sticks installed adding the other one afterward) or you can just mix them and run at the lower speed. Performance differences are very negligible.