Mentioning below step by step guide with screen shots to connect .NET console application with Salesforce.
Generally the issue is in adding service reference.It you're unsure, try deleting the reference and adding it again.
If it is added succesfully, you'll get screen like this:
Also note while adding reference, you've to follow path like this in Visual Studio :
Project Name | Right click 'Add' | Service referece | Advanced | Add Web Reference
This will land you screen like above screen shot.
Revert in case of any further doubt.