Why don't my 3-way switches work like 3-way switches?
Take a look inside
If you look at an image of how the switches work internally, it makes it a bit easier to understand what's going on.

This Blog post contains images of the various states of different types of switch combinations, which might help you understand what's going on in the circuit.
The Truth behind the logic
A properly functioning set of 3-way switches, should function like an XNOR gate (or XOR gate depending on how it's hooked up).
XNOR
If both switches are in position 1 or 0, the light is on. If the switches are in opposing positions, the circuit is open and the light is off.
XOR
If both switches are in position 1 or 0, the light is off. If the switches are in opposing positions, the circuit is closed and the light is on.
The first step in troubleshooting multi-way switches, is to set up a truth table. With 3-way switches, the table should look something like one of these.

The best way to do this is to designate one switch as A and one as B, then say up is 1 and down is 0.  Then follow the input values in the table, and log the output. For the output, 1 means the light is on, and 0 means the light is off.

Start with both switches in the down position, and log the result.
Move switch B to the up position. Log the result.
Move switch B back to the down position, and flip switch A to the up position. Log the result.
Flip switch B back to the up position, and log the result.

Now that we can clearly see what is happening with the switches, we can start to diagnose the problem.
What are all these screws?
When installing 3-way switches, you'll notice there are 4 screw terminals.

Black(Common)
Brass(Traveler)
Brass(Traveler)
Green (Ground)

Ground
The bare (ground) wire in the circuit should be attached to the green (ground) screw.
Travelers
The travelers are interconnected between the two switches, so it doesn't really matter which traveler is connected to which brass screw. Though it's common practice to be consistent, so if the red wire is connected to the left screw at switch 1, it should be connected to the left screw at switch 2 as well.
Common
Finally, the common screw is used to connect either to the incoming power or the fixture, depending on which switch you're working on.  For example. Power (from the breaker) might enter at switch 1, so we'll connect the black (hot) wire from the incoming cable to the common screw on switch 1.  In this case, the common screw on switch 2 will connect to the switched wire to the fixture.
Neutrals and grounds
All the neutrals should be tied together, and all the grounds should be connected to all other grounds.
If you are not comfortable working with electricity, never hesitate to contact an Electrician.