After getting frustrated with Freya, I installed Linux Mint, thinking that the problem was OS dependent, but I faced the exact problem there as well. I was able to solve it as follows.
Step 1: Update the kernel
I don't think this step is necessary, but I also had the problem of pixelated logo screen before the login screen. Updating to the latest stable kernel rectified that. You can get the deb files from here. Just download the files and do this-
sudo dpkg -i *.deb
Step 2: Patching the linux kernel
My laptop has Realtek wireless device, and as I discovered, it's a common problem between linux kernel and Realtek devices. Get the drivers from https://github.com/lwfinger/rtlwifi_new. Download the project and-
sudo make install
sudo modprobe <driver-name>/<driver-name>.o
<driver-name> can be found in the output of the following command, under the
Wireless interface in the configuration field.
sudo lshw -C network
<driver-name> with the driver name, like in my case it was -