I would also go for a 5870, you can pick them up cheap sometimes and they are very good for mining.
In Canada they seem to cost more than a 6970.
Does the case have a standard ATX power supply? And is there an extra case fan (or at least place for it)?
There is an extra fan already. I'm not 100% sure that the existing PSU is ATX. I would buy a new PSU though, assuming it fits in the mid-tower of the Lenovo M57.