This is how 3-ways work
You have described what is utterly normal for 3-ways. If you don't like opposite=off, do as brhans says in his answer that he's about to write. And I'm with you, I do that all the time.
Or go another way with a relay
You can't just use random relays out of the Mouser catalog. However they make mains-wiring-listed relay modules legal for this, and they fit in a junction box knockout or inside a box.
Use a latching relay. This has two coils and a common. Energize one coil, the relay throws on and stays. Energize the other, the relay throws off and stays. Energizing need be only momentary.
You use these with a special momentary SPDT (in other words, a 3-way) switch that lives in the middle position until you push it up or down. Now you can use the 3-way switch wiring to carry common and two coils.