Troubleshooting 3-way switch
It sounds like you have power entering the junction box at the light fixture, then running to one of the switches. If you actually have power entering both switch boxes independently, this will never work and you need to look at the connections at the light fixture.

EDIT Here's a 3-way switch:



Here's what should be happening in your case in order for the switches to work:


One wire, entering one switch box, should be hot from the power source (if the circuit breaker is on, this wire is hot).
That hot wire should be connected to the common screw on the 3-way switch.
The travelers (the other two screws on the switch) should run straight from one switch to the other, with no other connections along the way, through the light fixture's j-box. (the travelers from each side will be connected to each other with wire nuts in the j-box, of course).
The wire that is attached to the common terminal on the other 3-way switch should be connected to the black wire on the light fixture. This is the power coming out of the switches.
The white wire on the light fixture should be connected (wire nut) directly to the neutral wire in the j-box under the light fixture. If you're using Romex, this is going to be the white wire in the 14-2 or 12-2 cable that supplies power into that j-box.


Here's another StackExchange answer that shows very simply how 3-way switches function.

And another very long, detailed answer (holy smoke, I thought my answer was too long).

This diagram shows 3-way switches with power entering the light fixture box, and seems less confusing than many. It's surprising how many mislabeled diagrams of 3-way switches there are out there:


http://cindyjerrell.com/artwork/2012554_3_Way_Switch_Wiring_Diagram.html

A little more explanation

There are different ways to physically wire up 3 way switches, depending on whether power enters one of the switch boxes or enters the switched fixture. But they all add up to exactly the same thing.

You have 3 terminals on each switch. The different-colored one (usually darker) is the common, and the other two are "travelers."

So you have 2 travelers. This is usually the red and white, if your wiring is NM/Romex 3-rope, and you would use a black permanent marker or wrap black tape around the end of the white wire to indicate it is a hot conductor (not a neutral) in the switch circuit.

It sounds like you have something other than NM 3-rope going on in the wall between the light fixture and one of the switches (not the end of the world--electricity doesn't care about the color of the insulation on the wire).

The travelers always run straight between the same-colored terminals on both 3-way switches, no other connections

Depending on the positions of the switches, one of the travelers is always hot.

If the switches are positioned so that the common on both ends is connected to the hot traveler (which could be either traveler), then the circuit is complete and the light comes on.

The purpose of the travelers is to complete or break an electrical connection between the common terminals on the 3-way switches.

Now that the travelers are out of the way (connect them to the two same-colored terminals on the switches, forget about them), consider the common terminals...

Regardless of where the power enters the circuit, you run your hot wire to the common terminal on one switch, and wire the hot lead on your fixture to the common terminal on the other switch.

The entire set of 3-way switches, as a whole, just switches the juice on the common terminal of the 3-way switch at the opposite end.