Electrical – Switch has two red wires

Not knowing which brand you are using, I just googled double stacked switches, saw the Leviton 5224-2W and noticed the black screws are for the switch legs going to each light while the brass screws are for the hot common, which are typically bridged together with a removable fin (or "tab" as Brad Gilbert mentioned). If the fin has been removed, you will have to create a bridge with wire to feed both switches. When connecting, use the brass screw(s) for the constant hot and the black screws for the independent switch legs. If the connections are mis-arranged on the switch you would have the issue as you describe.

In pictorial form, if you have this:

You'll need to do this instead: The Black and White coming in from the bottom would represent your hot/neutral feed at the switch. This is assuming some things, as your feed could just as well come in at one of the lights. A few pictures from your end would help if this does not look like what you have.

Conventional Switches

It sounds as if most of the switches you have been replacing are single pole switches. That is, they make (on) or break off) a single connection from one location.

Simple switches use a black (hot) and another wire, usually black, red or blue (switched hot) to make and break the circuit. Basic switches do not need a neutral wire (white), so the neutral in a switch box is sometimes capped.

Smart Switches

Smart switches, like the Insteon, often also require a neutral (white) wire. The ground wires should be present and connected on all modern switch connections.

Conventional 3-way Switches

When a light is controlled from two locations, you need a switch called a 3-way. A basic 3-way switch has a black wire or connector, called a common, and two traveler wires, usually black, red or blue. The two travelers may be the same color or different colors, but the switch itself will usually be marked. It also should have a ground.

The common wire on one of the 3-ways is connected to the incoming hot line. The common on the other switch is connected to the fixture or outlet being controlled. The two travelers are connected to the traveler terminals on the opposite switch.

This setup allows either switch to change the state of the fixture by changing which traveler is connected. When both switches are on the same traveler, the light is on. When the switches are on different travelers, the light is off. A flick of either switch can make or break the connection.

When you want a smart switch, the 3-ways often need to add a neutral (white). This is always connected to the neutral line of the circuit (other white wires) and not to a hot or a switched hot wire.

WiFi Switches

If you want to control a fixture from two locations with an Insteon type switch, you need 3-way setup. However, these types of switches do not need two travelers, just a single connecting wire. They communicate the change of state (on or off) wirelessly between the switches, and the hub if it uses one.

The wiring directions for a 3-way connection can be found here, at the Insteon site. The following is a picture of the 3-way setup.

You can see that at the switch where the hot line comes in, the line hot, switch hot, and one of the traveler line (in this illustration black) are all connected. The other traveler (red in the illustration) is not used so it is capped.

In the second box that holds the cable to the fixture, the active traveler from the first box is connected to the black to the second switch, and the red from the second switch is connected to the fixture. The second, unused traveler is also capped.

If your two travelers are both red, you need to figure out which one is the connected one and which one is the unused one. Sometimes the wires have a marking, such as a stripe to help distinguish. If not a simple trial and error approach will work. If you pick the wrong one for the second switch, it simply will not work. you can then swap the traveler wires in the second box and you should be fine. Be sure to cap the unused wires.