The gramota.ru website has a (new?) online course, which seems to be free, for Russian learners. I think it's aimed at beginners or near-beginners. I've only looked at the first story, but it seems to be really superb! I really enjoyed listening to / reading the first bit, although it's a bit too basic for me.
http://www.learning-russian.gramota.ru/ ... /index.htm
By the way, it will probably help to have broadband, although I had no trouble listening to the audio on dial-up.
The English guy is called 'Sherlock Higgins' .. but I think I'm in love with Agata