Having a clean installation of Ubuntu 14.04 I use a simple way to get boinc to work:

sudo apt-get update
sudo apt-get install boinc-client

That's all, Initially it should work, and works like a charm on my vps. But when I'm trying to setup boinc on another vps, I'm having the same error 'can't connect to local host' when trying to attach a new project\get anything\check status etc.

root@vps2:~# boinccmd --project_attach URL auth
can't connect to local host

The only concern I have is that the port 31416 is'n working. For example, I have a clean installation of ubuntu 14.04 on another vps hosting and have this result with netcat command:
root@vps1:~# nc -v localhost 31416
localhost.localdomain [127.0.0.1] 31416 (?) open

Checking the same port with CLEAN ubuntu with the same netcat command:
root@vps2:~# nc -v localhost 31416
localhost.localdomain [127.0.0.1] 31416 (?) : Connection refused

It's really confusing, because I have no luck with vps provider support, they keep saying that there's no firewall or port restriction from their side and that it must be a problem with my local settings.
I'd greatly appreciate any help.

I figured out that it can be a problem with boinc-client itself:

root@vps2:/# service boinc-client start
* Starting BOINC core client: boinc [ OK ]
* Setting up scheduling for BOINC core client and children: [ OK ]
root@vps2:/# nc -v localhost 31416
localhost.localdomain [127.0.0.1] 31416 (?) open

And after a couple of seconds:

root@vps2:/# nc -v localhost 31416
localhost.localdomain [127.0.0.1] 31416 (?) : Connection refused
root@vps2:/# service boinc-client status
* Status of BOINC core client: stopped

Yes, that would explain the symptoms. You cannot connect to local host - the client - if the client isn't running.

The next job would be to locate any crash dump file, (boinc itself might have written error messages into stdoutdae.txt or stderrdae.txt), and try to interpret them.