As a meta-answer, consider the attack types:
Active attacks on the line: the bad guys plug on the line, observe the communication, and interfere with it. When both Alice and Bob have done their games with passwords or whatever, and are both convinced that they talk to the right person, the attackers cut the line and promptly redirect both conversations to Charlie and Deborah, who imitate the voices of, respectively, Bob and Alice. Charlie talks to Alice, Deborah talks to Bob. This is a full (wo)man in the middle attack and it is unavoidable. Conceptually, this means that authentication is relative to the exchanged data; if you just authenticate the line then you are trusting the network for being immune to active attacks. Therefore, in your model, you must assume that such active attacks do not happen.
Passive attacks on the line: also known as "eavesdropping". This is a well-known kind of attack practised by law enforcement agencies and spies all over the world, and it predates phones, too. For a simple authentication issue, eavesdropping is not a danger, since passive attackers, by definition, are passive: they do not prevent or interfere with communications. But they may learn quite a lot, and use that ill-gotten knowledge to help the third kind of attacker (see below).
Impersonation: Charlie or Deborah tries to impersonate Bob or Alice when talking to Alice or Bob. This is a weakened variant of the full active attack explained above, in that the attacker does not get to hijack an ongoing conversation; he must start right away. In order to avoid an eavesdropper learning enough to perform an ulterior impersonation, the protocol must not be fully deterministic; otherwise, a replay attack is possible (simply put, Charlie says to Alice exactly what Bob said to Alice the day before).
A special note must be made about simultaneous double impersonation: this is a variant of the MitM attack, in which Charlie calls Alice and Deborah calls Bob simultaneously; Charlie and Deborah are in adjacent rooms and have ear plugs so that both can hear both conversations; they then "forward" messages between Alice and Bob. This is the "low tech" variant of the active attack explained above. That variant can be averted by using an extra characteristic: during a normal phone call, one participant is the caller, and both participants know which one is the caller. In the double impersonation setup, Alice and Bob are both "receivers". So the authentication protocol must be asymmetric: the caller/receiver role MUST be used in the choice of challenges/answers.
So you end up, basically, with the solution shown by Jeff Ferland: a challenge/response protocol, where challenges and responses are one-time passwords. Alice/Bob must never reuse a challenge, or accept to respond to a reused challenge. To prevent simultaneous double impersonation, an extra convention must be enforced: receiver talks first. In Jeff's protocol, Alice will send a challenge ("what is word number 17 in the list ?") to which Bob must respond; and Bob will also send a challenge to Alice, to which Alice must respond. Let's add the extra convention: if Alice calls Bob, then Bob must issue the first challenge; Alice will send here challenge only after responded to Bob's challenge. In the MitM scenario, both Charlie and Deborah are callers, so they both receive challenges, and have no response to feed on. And now it is safe (up to confidentiality issues with eavesdroppers, and in-conversation hijack by powerful attackers, both of which being deadly, and can be thwarted only with cryptography).
