I was thinking about how a 4-way is wired. You wire it in pairs so, even though 4-way has 4 wires and 4 screws, you still have a 50-50 chance to wire it correctly.
With a 3-way, on the other hand, you only have a 1 in 3 chance of getting them right.
Also, if you screw up the 4-way nothing will work. If you get it right, then one of the 3 ways will work.
So the OP must have had the 4-way correct.