I had the very same problem and here's the solution which was helpful to me:
The message you are getting when you switch on vidalia and consequently when vidalia tries to connect you to the tor network is because tor is set run on startup, meaning when you start vidalia there is already an instance of tor running on your OS and therefore it can't start another(maybe tor is programmed to one instance per session).
Since tor is already running, use
sudo ps -ax |grep tor to confirm, all you need is to configure your browser to route traffic through tor which i suppose you haven't. See "Browser config" below.
If you want to operate, customize and/or switch on/off tor easily without the cryptic CLI then you might want to use vidalia. And for that:
sudo killall tor so that vidalia can launch tor as its child
then ask vidalia to connect you to the tor network and hopefully it will work.
Set your browser to use SOCKS proxy (v5 works, haven't tested it for v4) , ip address:127.0.0.1 and port:9050 when you want to use tor otherwise do not disturb this.
Note that tor will automatically run on each startup, so you'll have to kill it on each and every startup if you want to connect to tor using vidalia. The automatic cure to that which i choose was to use upstart because i didn't want to dig in the tor configs. Squashing is relatively easier.
If your ISP requires you to connect to the internet through proxy server then you'll have to set vidalia to use that proxy setting in order to connect to tor.
Note to readers i aint an expert hacker and many a things i've stated here are based on my observation which seemed quite plausible and might be wrong so please make corrections where ever needed.