Ok, don't look at the diagram for a minute (its right, just maybe slightly more confusing). For a 3-way to work the first thing you need is a pair of wires (called travelers) that run from one switch to the other with nothing else connected to them. This would be the red and black wires in a piece of 14-3. Now if you look at a 3-way switch there will be one screw that is a different color. Do not connect the travelers to this screw, connect the red and black travelers to each of the other screws. It does not matter which you connect the red or the black to. (If your are going to do it the way your diagram shows you need to be sure you don't screw up which piece of 14-2 is carrying your travelers between the fixtures.)
On wall A connect the hot(black) wire to the remaining screw on the 3-way switch and connect the white(neutral) to the white wire that belongs to the 14-3.
Now for the second 3-way. Run a piece of 14-2 from fixture one, to fixture 2 and then down to the second 3-way. Connect your light fixtures (white to white, black to black). At the second 3-way connect the black wire from you 14-2 to the remaining unused terminal on your 3-way and the white wire to the white wire from the 14-3. Your done.
Basically for a 3-way setup to work you apply power at one 3-way, have a pair of travelers connecting the 2 three ways together and connect your lights at the other 3 way. Its done this way in the diagram, just not as clearly because of the way the neutral/white wire is run.
Also I've seen plenty of bad 3-way switches. If your sure the wiring is correct go to a different store, buy two more 3-ways and swap them out. (Bad 3-ways sometimes come in batches hence the reason for a different store).
-rick