How to fix "married" light switches that have been wired in series?
You should be able to rewire it to work the way you want if they are three-way switches.

Here's a diagram from Wikipedia:


Here's what the behaviour should be:


Switch 1    Switch 2    Light is
On          Off         On
Off         On          On
Off         Off         Off
On          On          Off


See further explanation on Wikipedia