Folks, I finally managed to pair my headset with the phone. It is working fine now. Here is what I was doing wrong. I was trying to pair my device with the phone by just switching on the device and scanning for devices on my phone. When I try to scan, the device would not show up on the list.
This is because, the device was not in pairing mode. In the Plantronics Discovery 925, you need to switch off the device, power it on back by holding the power button and keep holding it until it flashes red and blue. This is when the device gets into pairing mode and it shows up on the phone's list. All this has to be done while the phone's bluetooth is ON and it is scanning for devices.
Hope this might help someone. My thanks to all those who cared to reply.