Thought I would offer some advice that has worked for me in the past. I was a helpdesk manager for 2 years, and found after some trial and error these few things could help address your concerns.
First with customer service:
Come up with a standard Help Desk greeting, maybe perhaps even asking Sr. Mgmt about renaming it something like Customer Support, this will help get your techs in a customer service mindset. Whatever greeting you decide on make it mandatory that they say it at the beginning of every call. A closing is nice, but it annoys some people.
If you aren't are monitoring their calls, you should be. Listen in on 2 for each analyst you have. Come up with a critera sheet. After each monitoring tell them what needs improved, and what they did well on. Nothing feels better than for your mgr to tell you that you are doing a good job. Esecially with phone support.
There is one important thing you need to drive home again and again to your employees. Empathy. If you can teach them to convey empathy over the phone, that will improve soft skills ten fold. On your monitoring criteria make empathy the heaviest weighted category. If they can put themselves in the shoes of the person on the other end, not only will softskills improve, but so will their accountability and their willingness to take ownership of problems. When they start to hear prasies from the customers/employees about how they had been suffering with this problem for sooo long..and how no one else could fix it but them, all of it will start to tie together and become second nature to the analysts.
As far as getting their troubleshooting skills in order. First thing is you need to test them and see where the best skills are at, and any common skills that all of them may need. Give them dailey assignments, not like homework or anything, just something simple like for a week give them terms to search online for. At the end of the week have them explain what those terms are, not the book definition, but make them show you they understand what it means. Make them learn what .ini, .dat, DLL, illegal operations, and GPF's are for example. Have them explain how they can use it in their own job. Keep doing that until they understand how nearly everything works in and with Windows. Teach networking skills to those who don't have them.
When you teach them something, they need to be able to relate it to what they are doing. The best way I found to do this is make sure they understand that one of the best troubleshooting skills is the process of elimination, deductive reasoning. The analysts need to be able to immediately think of all the things something CAN'T be when a customer describes a problem, instead of what they think it is. It will save them loads of time, and frustration. Go over each of the common issues they encounter with them this way. Hold weekly meetings so you can tell them what they are doing well, and what all of them as a team need to work on. Encourage the exchange of information between them. Create a distro in outlook if you have access to it, that is only for the exchange of information amongst them. Perhaps depending on how many their are, let them keep chat clinets open to talk to each other. In the tech support game its not always about if you know the answer, but more so if you can find it.
Have an analyst with the best technical skills update you every day with issues that have arisen, and any known solutions or fixes. These guys know more about what is going on with the systems, and the users than anybody. Then email that update to your entire team.
Also have the analyst that has the best empathetic and customer service qualities update every week with you so that you can gauge on how the users are feeling about the service they are getting from the help desk.
This motivates both employees to be the best at what they do because you have recognized them, and giving a little extra responsibility goes a long way toward self-esteem. Make it known to the other employees that if they want such things, to learn as much as they can, and if you seem great improvements, reward them.
If your employees know you can do their job with your eyes closed, and that you have been there before, they will respect you. If they feel you are on their side, and not another suit, they will want to improve.
The most important thing is to give constant feedback. Never tell someone that they are doing something wrong without making a point over something they did correctly.
Set goals with each one, and for each goal they meet reward them. Even if its giving an extra break, or taking their calls for an hour. No matter how small the reward, most people will work harder if they know there is something else in it for them.
2 last things.
Make your agents use a notes template for every call they do. Most all ticketing/call tracking software has a summary field that you can copy and paste to. Have the users keep notepad open with blank templates in them, fill them out as they go along, then copy into the software. This way all their notes are consistent, other members of the Dept will appriciate getting the information they need every time.
You can try something like this.
NAME
(ANY RELEVANT CONTACT INF0)
OS
ANY ID's(printer, and workstation names)
DESCRIPTION OF THE PROBLEM
ERROR MSG RCVD
STEPS TAKEN DURING CALL
PC REBOOTED IN PAST 12 HRS?
ANY RECENT CHANGES?
WHEN DID THEY FIRST NOTICE PROBLEM?
ADDITIONAL COMMENTS
Of course you will need to tailor it to your needs but just a rough idea. Also poll any other dept that they submit trouble tickets to and ask them what information they would like to see on their tickets, and what steps the analysts should always be taking before a ticket is even submitted.
I hope this helps you. Sorry this was so long winded. These are just things I have had sucess with, and always wished my mgrs would have done with me.
Good Luck! Once you see improvement, you'll feel like superman