"Is it possible for a medium (here calcite) to have two refractive indices?"
Yes. Birefringence refers to the property that the refractive index of a material depends upon the polarization or direction of light through the material.
Refractive index describes the speed of propagation of light in a medium. So to restate your question:
why is the speed of light slower in some media than in others?
The wave equation tells us that speed of propagation depends on two factors: one is an inertial term, while the other is an elastic term. Let's look at a simple case of a string. The velocity of wave propagation in a string goes as
$$v = \sqrt\frac{T}{\mu}$$
where $T$ is the tension, and $\mu$ is the mass per unit length.
When light propagates in a dielectric medium, the electrons in that medium are moved by the EM field of the light. These moving electrons in turn emit an electromagnetic wave, but this wave will be lagging in phase with the signal that caused their motion.
Because of this phase lag, the combined signal that propagates is the sum of the initial signal (now a bit smaller because it gave some of its energy to the electron) plus the phase-shifted signal from the electron. Together, they create a phase shift in the original signal - it is as though it is going slower.
The shift due to one electron is tiny; but the more electrons you have per unit volume, the greater the effect will be. The actual force with which the electrons are bound (the "elastic constant" if you like) also comes into play, so you can't simply say that refractive index scales with density - but for similar materials, it does; the following graph (from http://upload.wikimedia.org/wikipedia/en/3/3b/Density-nd.GIF) shows that similar materials with different densities have a pretty believable relationship between density and refractive index:
The wikipedia page on refractive index contains some more information on the topic...
Best Answer
Light is refracted on the way in and on the way out. The refractive index varies with the wavelength of the light, red being refracted less than blue.
If the "in" and "out" faces of the prism were parallel then the difference in refraction effectively cancels out - look through a window and light directions are not changed. But in a triangular prism the "cancelling " doesn't happen. You can see this if you draw a ray diagram, consult an elementary level book on optics, or just look at the above diagram.