I'm learning welsh from the BBC website http://www.bbc.co.uk/wales/learnwelsh/bigwelshchallenge/
It's free and the best online learning resource I have found. Also it comes in either North or South versions, which is useful for me cos I want to learn 'North' and most courses seem to be mainly in 'South' (including the OU one - although they say they include some 'North').
Personally I have used Rosetta Stone and I found it wasn't really for me - you can download a sample from their website before you buy. http://www.rosettastone.co.uk/personal/demo
I have studied with the OU before (maths and psychology, not languages, though) and I can recommend their courses. The welsh course says it is suitable for complete beginners, but if you are nervous why not spend some time on a free course like the BBC one above, and then move onto the OU one?