Figured it out. Did these two things -
$ sudo vim /etc/default/beanstalkd
> START yes # uncomment
$ sudo service beanstalkd start
# Alternatively: /etc/init.d/beanstalkd start
Got it from this link - http://fideloper.com/ubuntu-beanstalkd-and-laravel4