Hello Gaurish,
I have had this same issue at work.
One of the issues is with the config files for the service and the client. Make sure that the web protocols in the service config match with the client config protocols. Windows Phone 7 does not work with the wsHttpBinding. So you will probably want to use the basicHttpBinding.
Also, once you have added a service reference, it is best to build the project straight away. I have found that VS2010 doesn't always generate the code for References.cs. If you click on the show all files button on the solution explorer, and then navigate to the References.cs file, can you see the generated code?
If all else fails, follow this tutorial:
Creating a Windows Phone 7 Application consuming data using a WCF Service by Urmimala Pal. Once you have got the project working, study the service and config files, and References.cs file. What are the differences between the tutorial project and your own project? Does applying these differences to your own project work?
The problem when deploying to a physical device is that if you house a web service on your local network, it is unavailable to the windows phone. However, if you make your web service accessible over the internet then you should have no problem connecting when you come to do a live test.
The main problems I experienced were down to the configuration files being incorrectly configured. This may be the problem you are experiencing. Try deleting your service references and client config file and try again.
I hope this information will be helpful.
Kind Regards,
Jason.