Unfortunately, there are a number of ways that 3-way systems can be installed, and it can be a little hard to figure out which way its done.

Based on your wire colors, it sounds to me like you have a system where the power comes to one of the switches, the hot (one of the blacks) goes to the switch, the neutral bypasses the switch all the way to the lamp, the other black and the red go to the other switch, and the final black is run between the other switch and the lamp.

If you have a multimeter, you should be able to verify this. With everything unconnected, only one of the black wires at one of the switches should have power. (Be careful, obviously.)

The way that GE apparently wants this all to work is that one is a primary switch that does all the logic and the other is a dumb (single-pole) switch. If that's the only way to do it, you'll have to rewire, effectively pulling one of the black wires from the second switch back to the first switch.

Maybe they make a different kind of 3-way switch for your application?